Cod sursa(job #2814863)

Utilizator AndreeaGherghescuAndreea Gherghescu AndreeaGherghescu Data 8 decembrie 2021 18:31:22
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

#define INF 1e9

int n,m;
int rmat[101][101], jmat[101][101];
int dl[] = {0,0,1,-1,1,-1,1,-1};
int dc[] = {1,-1,0,0,-1,1,1,-1};

int validr (int x, int y) {
    if (x<1 || y<1 || x>n || y>m)
        return 0;
    return 1;
}
int validj (int x, int y) {
    if (x<1 || y<1 || x>n || y>m)
        return 0;
    return 1;
}

void leer (int xstart, int ystart) {
    deque < pair<int,int> > q;
    q.emplace_back(make_pair(xstart, ystart));
    while (!q.empty()) {
        pair <int,int> key = q.front();
        q.pop_front();
        int i = key.first;
        int j = key.second;

        for (int d = 0; d < 8; d++) {
            int ii = i + dl[d];
            int jj = j + dc[d];

            if (!validr(ii,jj) || (rmat[ii][jj] != 0 && rmat[ii][jj] <= rmat[i][j] ))
                continue;

            rmat[ii][jj] = rmat[i][j] + 1;
            q.emplace_back(ii,jj);
        }
    }
}

void leej (int xstart, int ystart) {
    deque < pair<int,int> > q;
    q.emplace_back(make_pair(xstart, ystart));
    while (!q.empty()) {
        pair <int,int> key = q.front();
        q.pop_front();
        int i = key.first;
        int j = key.second;

        for (int d = 0; d < 8; d++) {
            int ii = i + dl[d];
            int jj = j + dc[d];

            if (!validj(ii,jj) || (jmat[ii][jj] != 0 && jmat[ii][jj] <= jmat[i][j] ))
                continue;

            jmat[ii][jj] = jmat[i][j] + 1;
            q.emplace_back(ii,jj);
        }
    }
}

int main () {
    in >> n >> m;
    in.get();
    int rx,ry,jx,jy;
    for (int i = 1; i <= n; i++) {
        string line;
        getline(in, line);

        for (int j = 1; j <= m; j++) {
            char chr = line[j-1];

            if (chr == 'X') {
                rmat[i][j] = -1;
                jmat[i][j] = -1;
            }
            else if (chr == ' ') {
                rmat[i][j] = 0;
                jmat[i][j] = 0;
            }
            else if (chr == 'J') {
                rmat[i][j] = 0;
                jmat[i][j] = 1;
                jx = i, jy = j;
            }
            else if (chr == 'R') {
                rmat[i][j] = 1;
                jmat[i][j] = 0;
                rx = i, ry = j;
            }
        }
    }

    leer(rx,ry);
    leej(jx, jy);


    int x,y, best = INF;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (rmat[i][j] == jmat[i][j] && rmat[i][j] < INF && rmat[i][j]>0) {
                x = i;
                y = j;
                best = rmat[i][j];
            }
        }
    }
    out << best << ' ' << x << ' ' << y << '\n';
    return 0;

}