Cod sursa(job #3291321)

Utilizator mateilbMatei Balaur mateilb Data 4 aprilie 2025 09:38:17
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.87 kb
#include <bits/stdc++.h>

using namespace std;
int mat1[105][105];
int mat2[105][105];
int dirl[4] = {-1, 0, 1, 0};
int dirc[4] = {0, 1, 0, -1};
struct elem {
    int l, c;
} coada[105 * 105];
int main() {
    ifstream cin("rj.in");
    ofstream cout("rj.out");
    int n, m, linie, coloana, ans = 0, minn = INT_MAX;
    cin >> n >> m;
    cin.get();
    int ir, jr, ij, jj;
    char c;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin.get(c);
            if (c == 'X') mat1[i][j] = -1, mat2[i][j] = -1;
            else if (c == ' ') mat1[i][j] = 0, mat2[i][j] = 0;
            else if (c == 'R') {
                mat1[i][j] = 0;
                ir = i;
                jr = j;
            } else if (c == 'J') {
                mat2[i][j] = 0;
                ij = i;
                jj = j;
            }
        }
        cin.get();
    }
    /* for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= m; j++) {
             cout << mat1[i][j] << " ";
         }
         cout << "\n";
     }*/
    for (int i = 0; i <= n + 1; i++)
        mat1[i][m + 1] = -1,mat1[i][0] = -1;
    for (int j = 0; j <= m + 1; j++)
        mat1[n + 1][j] = -1,mat1[0][j] = -1;
    for (int i = 0; i <= n + 1; i++)
        mat2[i][m + 1] = -1,mat2[i][0] = -1;
    for (int j = 0; j <= m + 1; j++)
        mat2[n + 1][j] = -1,mat2[0][j] = -1;
    int sf = 1, inc = 1;
    coada[1].l = ir;
    coada[1].c = jr;

    mat1[ir][jr] = 1;
    while (inc <= sf) {
        for (int x = 0; x < 4; x++) {
            int lin = coada[inc].l + dirl[x];
            int col = coada[inc].c + dirc[x];
            if (mat1[lin][col] == 0) {
                sf++;
                coada[sf].l = lin;
                coada[sf].c = col;
                mat1[lin][col] = mat1[coada[inc].l][coada[inc].c] + 1;
            }
        }
        inc++;
    }
    sf = 1, inc = 1;
    coada[1].l = ij;
    coada[1].c = jj;
    mat2[ij][jj] = 1;
    while (inc <= sf) {
        for (int x = 0; x < 4; x++) {
            int lin = coada[inc].l + dirl[x];
            int col = coada[inc].c + dirc[x];
            if (mat2[lin][col] == 0) {
                sf++;
                coada[sf].l = lin;
                coada[sf].c = col;
                mat2[lin][col] = mat2[coada[inc].l][coada[inc].c] + 1;
            }
        }
        inc++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
           // cout << mat1[i][j] << " " << mat2[i][j] << "\n";
            if (mat1[i][j] == mat2[i][j] && mat1[i][j] != -1 && mat1[i][j] != 0) {
                if (mat1[i][j] < minn) {
                    minn = mat1[i][j] - 1;
                    linie = i;
                    coloana = j;
                }
            }
        }
    }

    cout << minn << " " << linie << " " << coloana;
    return 0;
}