Cod sursa(job #3208854)

Utilizator XTrim07Florea Andrei XTrim07 Data 1 martie 2024 11:19:45
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda 1_martie_simulare_oji_2024_clasa_10 Marime 2.24 kb
#include <bits/stdc++.h>
using namespace std;

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

const int INF = 9999999;

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

char mt[102][102];
int rx, ry;
int jx, jy;

int rm[102][102];
void romeo() {
    queue<pair<int, int>> q;
    q.push({rx, ry});
    rm[rx][ry] = 0;
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        for (int i = 0; i < 8; ++i) {
            int x = p.first + dx[i];
            int y = p.second + dy[i];
            if (rm[x][y] > rm[p.first][p.second] + 1 && mt[x][y] != 'X') {
                rm[x][y] = rm[p.first][p.second] + 1;
                q.push({x, y});
            }
        }
    }
}

int jm[102][102];
void julieta() {
    queue<pair<int, int>> q;
    q.push({jx, jy});
    jm[jx][jy] = 0;
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        for (int i = 0; i < 8; ++i) {
            int x = p.first + dx[i];
            int y = p.second + dy[i];
            if (jm[x][y] > jm[p.first][p.second] + 1 && mt[x][y] != 'X') {
                jm[x][y] = jm[p.first][p.second] + 1;
                q.push({x, y});
            }
        }
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    fin.getline(mt[0] + 1, m + 1);
    for(int i = 1; i <= n; ++i) {
        fin.getline(mt[i] + 1, m + 1);
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(mt[i][j] == 'R') {
                rx = i;
                ry = j;
            }
            else if(mt[i][j] == 'J') {
                jx = i;
                jy = j;
            }
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            rm[i][j] = INF;
            jm[i][j] = INF;
        }
    }   
    romeo();
    julieta();
    int tmin = INF;
    int x, y;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(rm[i][j] == jm[i][j] && rm[i][j] < tmin) {
                tmin = rm[i][j];
                x = i;
                y = j;
            }
        }
    }
    fout << tmin + 1 << " " << x << " " << y;
    return 0;
}