Cod sursa(job #2857679)

Utilizator CalinHanguCalinHangu CalinHangu Data 26 februarie 2022 08:43:20
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <queue>

using namespace std;

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

int r[105][105], ju[105][105], di[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dj[] = {0, 1, 1, 1, 0, -1, -1, -1}, n, m, i, j;
char a[105][105];
queue < pair <int, int> > Q;

bool inmat(int x, int y)
{
    return x >= 0 && x < n && y >= 0 && y < m;
}

void Lee1(int istart, int jstart) {
    r[istart][jstart] = 1;
    Q.push({istart, jstart});
    while(! Q.empty()) {
        int i = Q.front().first;
        int j = Q.front().second;
        for(int k = 0 ; k < 8 ; ++k) {
            int iv = i + di[k];
            int jv = j + dj[k];
            if(inmat(iv, jv) && (r[iv][jv] == 0 || r[iv][jv] > r[i][j] + 1))  {
                r[iv][jv] = r[i][j] + 1;
                Q.push({iv, jv});
            }
        }
        Q.pop();
    }
}

void Lee2(int istart, int jstart) {
    ju[istart][jstart] = 1;
    Q.push({istart, jstart});
    while(! Q.empty()) {
        int i = Q.front().first;
        int j = Q.front().second;
        for(int k = 0 ; k < 8 ; ++k) {
            int iv = i + di[k];
            int jv = j + dj[k];
            if(inmat(iv, jv) && (ju[iv][jv] == 0 || ju[iv][jv] > ju[i][j] + 1))  {
                ju[iv][jv] = ju[i][j] + 1;
                Q.push({iv, jv});
            }
        }
        Q.pop();
    }
}

int main()
{
    int minv = 1e9 + 1, imin, jmin, ir, jr, ij, jj;
    in >> n >> m;
    in.get();
    for(i = 0 ; i < n ; ++i){
        in.getline(a[i], 105);
        for(j = 0 ; j < m ; ++j){
            if(a[i][j] == ' '){
                r[i][j] = 0;
                ju[i][j] = 0;
            }

            if(a[i][j] == 'X'){
                r[i][j] = -1;
                ju[i][j] = -1;
            }

            if(a[i][j] == 'R') {
                ir = i;
                jr = j;
                r[i][j] = 0;
                ju[i][j] = 0;
            }

            if(a[i][j] == 'J') {
                ij = i;
                jj = j;
                r[i][j] = 0;
                ju[i][j] = 0;
            }
        }
    }
    Lee1(ir, jr);
    Lee2(ij, jj);
    for(i = 0 ; i < n ; ++i){
        for(j = 0 ; j < m ; ++j){
            if(r[i][j] == ju[i][j] && r[i][j]!= -1 && r[i][j] != 0) {
                    if(r[i][j] < minv){
                        minv = r[i][j];
                        imin = i;
                        jmin = j;
                    }
            }
        }
    }
    out << minv << " " << imin + 1 << " " << jmin + 1 ;
    return 0;
}