Cod sursa(job #3171133)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 18 noiembrie 2023 13:41:22
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 100;
char a[NMAX + 1][NMAX + 1];
int n, m;
int timpR[NMAX + 1][NMAX + 1], timpJ[NMAX + 1][NMAX + 1];
int xr, yr, xj, yj;
int dx[] = {0, 0, 1, -1, -1, 1, 1, -1};
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1};

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

int main() {
    f >> n >> m;
    f.get();
    for(int i = 1; i <= n; i++) {
        string s;
        getline(f, s);
        for(int j = 0; j < m; j++) {
            if(s[j] == 'X') {
                timpR[i][j + 1] = timpJ[i][j + 1] = -1;
            } else {
                if(s[j] == 'R') {
                    xr = i;
                    yr = j + 1;
                }
                if(s[j] == 'J') {
                    xj = i;
                    yj = j + 1;
                }
            }
        }
    }
    queue<pair<int, int>> q;
    q.push({xr, yr});
    timpR[xr][yr] = 1;
    while(!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        for(int k = 0; k < 8; k++) {
            int nx = p.first + dx[k];
            int ny = p.second + dy[k];
            if(inside(nx, ny) && timpR[nx][ny] != -1 && timpR[nx][ny] == 0) {
                timpR[nx][ny] = timpR[p.first][p.second] + 1;
                q.push({nx, ny});
            }
        }
    }
    q.push({xj, yj});
    timpJ[xj][yj] = 1;
    while(!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        for(int k = 0; k < 8; k++) {
            int nx = p.first + dx[k];
            int ny = p.second + dy[k];
            if(inside(nx, ny) && timpJ[nx][ny] != -1 && timpJ[nx][ny] == 0) {
                timpJ[nx][ny] = timpJ[p.first][p.second] + 1;
                q.push({nx, ny});
            }
        }
    }
    int sx = 0, sy = 0;
    int mn = 1e9;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            //cout << timpR[i][j] << ' ';
            if(timpR[i][j] == timpJ[i][j] && timpR[i][j] > 0) {
                if(timpR[i][j] < mn) {
                    mn = timpR[i][j];
                    sx = i;
                    sy = j;
                }
            }
        }
        //cout << '\n';
    }
    g << mn << ' ' << sx << ' ' << sy;
    return 0;
}