Cod sursa(job #2715900)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 4 martie 2021 13:00:51
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <queue>

using namespace std;

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

bool obs[N + 2][N + 2];
int dr[N + 1][N + 1], dj[N + 1][N + 1];

void bordare(int nl, int nc) {
    for (int i = 0; i <= nl + 1; ++i)
        obs[i][0] = obs[i][nc + 1] = true;
    for (int j = 1; j <= nc; ++j)
        obs[0][j] = obs[nl + 1][j] = true;
}

void lee(int xi, int yi, int d[N + 1][N + 1]) {
    queue<pair<int, int>> q;
    q.push({ xi, yi });
    
    int l, c;
    while (!q.empty()) {
        auto crt = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            l = crt.first + dx[i];
            c = crt.second + dy[i];
            if (!obs[l][c] && !d[l][c] && !(l == xi && c == yi)) {
                d[l][c] = d[crt.first][crt.second] + 1;
                q.push({ l, c });
            }
        }
    }
}

int main() {
    ifstream in("rj.in");
    ofstream out("rj.out");

    int nl, nc, xr, yr, xj, yj;
    char s[N + 1];
    in >> nl >> nc;
    in.get();
    for (int i = 1; i <= nl; ++i) {
        in.getline(s, N);
        for (int j = 1; j <= nc; ++j) {
            if (s[j - 1] == 'X')
                obs[i][j] = true;
            else if (s[j - 1] == 'R')
                xr = i, yr = j;
            else if (s[j - 1] == 'J')
                xj = i, yj = j;
        }
    }
    bordare(nl, nc);
    lee(xr, yr, dr);
    lee(xj, yj, dj);

    int x, y, dmin = 1 << 30;
    for (int i = 1; i <= nl; ++i)
        for (int j = 1; j <= nc; ++j) {
            if (!obs[i][j] && dr[i][j] && dr[i][j] == dj[i][j] && dr[i][j] < dmin) {
                dmin = dr[i][j];
                x = i, y = j;
            }
        }
    out << dmin << ' ' << x << ' ' << y;

    in.close();
    out.close();
    return 0;
}