Cod sursa(job #2658558)

Utilizator DawlauAndrei Blahovici Dawlau Data 14 octombrie 2020 12:27:05
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <deque>
#include <vector>
#include <string>
#include <climits>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");


const int moveRow[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int moveCol[] = {-1, 0, 1, 1, 1, 0, -1, -1};


int R, C;
int rowR, colR;
int rowJ, colJ;


vector < vector <int> > romeo;
vector < vector <int> > julieta;


void bord(vector < vector <int> > &grid){

    for(int row = 0; row <= R + 1; ++row)
        grid[row][0] = grid[row][C + 1] = -1;
    for(int col = 0; col <= C + 1; ++col)
        grid[0][col] = grid[R + 1][col] = -1;
}



void BFS(const int &startRow, const int &startCol, vector < vector <int> > &grid){

    deque < pair <int, int> > Queue;
    Queue.push_back({startRow, startCol});
    grid[startRow][startCol] = 1;

    while(!Queue.empty()){

        pair <int, int> Cell = Queue.front();
        Queue.pop_front();

        int row = Cell.first;
        int col = Cell.second;

        for(int dir = 0; dir < 8; ++dir){

            int newRow = row + moveRow[dir];
            int newCol = col + moveCol[dir];

            if(grid[newRow][newCol] == 0){
                Queue.push_back({newRow, newCol});
                grid[newRow][newCol] = grid[row][col] + 1;
            }
        }
    }
}


int main(){

    fin >> R >> C;

    romeo = vector < vector <int> >(R + 2, vector <int> (C + 2));
    julieta = vector < vector <int> >(R + 2, vector <int> (C + 2));

    string line;
    getline(fin, line);

    for(int row = 1; row <= R; ++row){

        getline(fin, line);

        for(int col = 0; col < C; ++col)
            if(line[col] == 'X')
                romeo[row][col + 1] = julieta[row][col + 1] = -1;
            else if(line[col] == 'R')
                rowR = row, colR = col + 1;
            else if(line[col] == 'J')
                rowJ = row, colJ = col + 1;
    }

    bord(romeo);
    bord(julieta);

    BFS(rowR, colR, romeo);
    BFS(rowJ, colJ, julieta);

    int tmin = INT_MAX;
    int ansRow = -1;
    int ansCol = -1;

    for(int row = 1; row <= R; ++row)
        for(int col = 1; col <= C; ++col)
            if(romeo[row][col] > 0 and julieta[row][col] > 0)
                if(max(romeo[row][col], julieta[row][col]) < tmin){

                    tmin = max(romeo[row][col], julieta[row][col]);
                    ansRow = row;
                    ansCol = col;
                }
                
    fout << tmin << ' ' << ansRow << ' ' << ansCol << '\n';
}