Cod sursa(job #2765512)

Utilizator Andrei_TudorAndrei Tudor Andrei_Tudor Data 27 iulie 2021 15:53:17
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <queue>
using namespace std;
 
vector <vector<int>> lee(pair <int, int> start, const int n, const int m, const vector<string> &mat){
    const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
    const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
    queue <pair <int, int>> Q;
    Q.push(start);
    vector <vector<int>> dist(n + 2, vector <int> (m + 2, 0));
    dist[start.first][start.second] = 1;
    auto isInside = [&n, &m](const pair <int, int>& cell) -> bool {
        return 1 <= cell.first && cell.first <= n && 1 <= cell.second && cell.second <= m;
    };
    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;
            }
            else if(dist[x.first][x.second] == 0){
                dist[x.first][x.second] = dist[cell.first][cell.second] + 1;
                Q.push(x);
            }
        }
    }
    return dist;
}

int main()
{
    ifstream cin("rj.in");
    ofstream cout("rj.out");
    int n, m;
    cin >> n >> m;
    pair <int, int> startr;
    pair <int, int> startj;
    vector <string> mat(n + 1);
    cin >> ws; // std::ws so whitespaces
    for(int i = 1; i <= n; i ++){
        getline(cin, mat[i]);
        mat[i] = "!" + mat[i];
        for(int j = 1; j <= m; j ++){
            if(mat[i][j] == 'R'){
                startr = {i, j};
            }
            else if(mat[i][j] == 'J'){
                startj = {i, j};
            }
        }
    }
    auto distr = lee(startr, n, m, mat);
    auto distj = lee(startj, n, m, mat);
    int tMin = 1 << 30;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(distr[i][j] == distj[i][j] and distj[i][j] > 0) {
                tMin = min(tMin, distr[i][j]);
            }
        }
    }
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(distr[i][j] == distj[i][j] && distr[i][j] == tMin){
                cout << distr[i][j] << " " << i << " " << j;
                return 0;
            }
        }
    }
    return 0;
}