Cod sursa(job #3159394)

Utilizator IleaIlea Bogdan Ilea Data 21 octombrie 2023 11:25:19
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
fstream fin("rj.in");
ofstream fout("rj.out");
int n, m;
int jl[101][101], ro[101][101];
pair <int, int> startj, startr, final_coord;
int rez_timp = INT_MAX;

void input()
{
    fin >> n >> m;
    char aux[101];
    fin.getline(aux, 2);
    for (int i=1; i<=n; i++){
        fin.getline(aux, 101);
        for (int k=0; k<m; k++) {
            if (aux[k] == 'X') {
                ro[i][k+1] = -1;
                jl[i][k+1] = -1;
            }
            else if (aux[k] == 'R') {
                startr.first = i;
                startr.second = k+1;
            }
            else if (aux[k] == 'J') {
                startj.first = i;
                startj.second = k+1;
            }
        }
    }
}

void border()
{
    for (int i=0; i<=n+1; i++){
        jl[i][0] = -1;
        jl[i][m+1] = -1;
        ro[i][0] = -1;
        ro[i][m+1] = -1;
    }
    for ( int j=0; j<=m+1; j++){
        jl[0][j] = -1;
        jl[n+1][j] = -1;
        ro[0][j] = -1;
        ro[n+1][j] = -1;
    }
}

int lin[] = {0, -1, 0, 1, 1, -1, 1, -1}, col[] = {1, 0, -1, 0, 1, -1, -1, 1};

void lee_julieta()
{
    queue <pair <int, int>> q;
    q.push ({startj.first, startj.second});
    pair <int, int> current, future;
    jl[startj.first][startj.second] = 1;
    while (!q.empty()){
        current = q.front();
        for (int i=0; i<8; i++){
            future.first = current.first + lin[i];
            future.second = current.second + col[i];
            if (jl[future.first][future.second] == 0) {
                jl[future.first][future.second] = jl[current.first][current.second] + 1;
                q.push ({future.first, future.second});
            }
        }
        q.pop();
    }

}

void lee_romeo()
{
    queue <pair <int, int>> q;
    q.push ({startr.first, startr.second});
    pair <int, int> current, future;
    ro[startr.first][startr.second] = 1;
    while (!q.empty()){
        current = q.front();
        for (int i=0; i<8; i++){
            future.first = current.first + lin[i];
            future.second = current.second + col[i];
            if (ro[future.first][future.second] == 0) {
                ro[future.first][future.second] = ro[current.first][current.second] + 1;
                q.push ({future.first, future.second});
            }
        }
        q.pop();
    }
}

void solve()
{
    lee_julieta ();
    lee_romeo ();
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if (ro[i][j] > 0 && jl[i][j] > 0) {
                if (ro[i][j] == jl[i][j]){
                    cout << "BLA";
                    if (ro[i][j] < rez_timp) {
                        rez_timp = ro[i][j];
                        final_coord.first = i;
                        final_coord.second = j;
                    }
                }
            }
        }
    }
    fout << rez_timp << ' ' << final_coord.first << ' ' << final_coord.second;
}

int main()
{
    input();
    border();
    solve();
    return 0;
}