Cod sursa(job #2765030)

Utilizator Andrei_TudorAndrei Tudor Andrei_Tudor Data 24 iulie 2021 15:28:53
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <fstream>
#include <queue>
using namespace std;
char mat[105][105];
int distr[105][105];
int distj[105][105];
ifstream cin("rj.in");
ofstream cout("rj.out");
int main()
{
    int n, m;
    char ch;
    pair <int, int> startr;
    pair <int, int> finishr;
    pair <int, int> startj;
    pair <int, int> finishj;
    cin >> n >> m;
    cin.get();
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            ch = cin.get();
            mat[i][j] = ch;
            if(ch == 'R'){
                startr.first = i;
                startr.second = j;
                finishj.first = i;
                finishj.second = j;
            }
            else if(ch == 'J'){
                startj.first = i;
                startj.second = j;
                finishr.first = i;
                finishr.second = j;
            }
        }
        cin.get();
    }
    const int dx[] = {0, 0, 1, 1, -1, -1, -1, 1};
    const int dy[] = {-1, 1, -1, 1, 1, -1, 0, 0};
    queue <pair <int, int>> Q;
    Q.push(startr);
    distr[startr.first][startr.second] = 1;
    auto isInside = [&n](const pair<int, int>& cell) -> bool {
        return 1 <= cell.first and cell.first <= n and 1 <= cell.second and cell.second <= n;
    };
    while(!Q.empty()){
        auto cell = Q.front();
        Q.pop();
        for(int direction = 0; direction <= 7; ++ direction){
            pair <int, int> x = {cell.first + dx[direction], cell.second + dy[direction]};
            if(!isInside(x) || mat[x.first][x.second] == 'X'){
                continue;
            }
            if(distr[x.first][x.second] == 0){
                distr[x.first][x.second] = distr[cell.first][cell.second] + 1;
                Q.push(x);
            }
        }
    }
    Q.push(startj);
    distj[startj.first][startj.second] = 1;
    while(!Q.empty()){
        auto cell = Q.front();
        Q.pop();
        for(int direction = 0; direction <= 7; ++ direction){
            pair <int, int> x = {cell.first + dx[direction], cell.second + dy[direction]};
            if(!isInside(x) || mat[x.first][x.second] == 'X'){
                continue;
            }
            if(distj[x.first][x.second] == 0){
                distj[x.first][x.second] = distj[cell.first][cell.second] + 1;
                Q.push(x);
            }
        }
    }
    bool ok = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(distr[i][j] == distj[i][j] && distr[i][j] != 0){
                cout << distr[i][j] << " " << i << " " << j << " ";
                ok = 1;
                break;
            }
        }
        if(ok == 1){
            break;
        }
    }
    return 0;
}