Cod sursa(job #3192863)

Utilizator stefanrotaruRotaru Stefan-Florin stefanrotaru Data 13 ianuarie 2024 13:21:34
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <fstream>
#include <queue>
#include <cstring>

using namespace std;

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

int dx[]={-1,-1,-1,0,1,1,1,0};
int dy[]={-1,0,1,1,1,0,-1,-1};

int n, m, Tmin = 1e9, costR[105][105], costJ[105][105], imin, jmin, Ri, Rj, Ji, Jj;

queue <pair <int, int> > q;

char ch[105];

bool inMat(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

void lee()
{
    q.push({Ri, Rj});

    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();

        for (int k = 0; k < 8; ++k) {
            int iv = i + dx[k];
            int jv = j + dy[k];

            if (inMat(iv, jv) && costR[iv][jv] == 0) {
                costR[iv][jv] = costR[i][j] + 1;
                q.push({iv, jv});
            }
        }
    }

    q.push({Ji, Jj});

    while (!q.empty()) {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();

        for (int k = 0; k < 8; ++k) {
            int iv = i + dx[k];
            int jv = j + dy[k];

            if (inMat(iv, jv) && costJ[iv][jv] == 0) {
                costJ[iv][jv] = costJ[i][j] + 1;
                q.push({iv, jv});
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if ((costJ[i][j] == costR[i][j]) && costJ[i][j] < Tmin && costJ[i][j] > 1) {
                Tmin = costJ[i][j];
                imin = i;
                jmin = j;
            }
        }
    }

    g << Tmin << ' ' << imin << ' ' << jmin;
}

int main()
{
    f >> n >> m;

    f.get();

    for (int i = 1; i <= n; ++i) {
        f.getline(ch, 105);
        for (int j = 1; j <= m; ++j) {
            if (ch[j - 1] == 'X') {
                costJ[i][j] = costR[i][j] = 1;
            }
            else if (ch[j - 1] == 'R') {
                Ri = i;
                Rj = j;
                costR[i][j] = 1;
                costJ[i][j] = 1;
            }
            else if (ch[j - 1] == 'J') {
                Ji = i;
                Jj = j;
                costJ[i][j] = 1;
                costR[i][j] = 1;
            }
        }
    }

    lee();

    return 0;
}