Cod sursa(job #3207706)

Utilizator MateiAlex24Diamandi Matei MateiAlex24 Data 26 februarie 2024 19:35:08
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int map_romeo[102][102], map_juliet[102][102], n, m;
int dir_i[4] = {0, -1, 0, 1};
int dir_j[4] = {1, 0, -1, 0};

int accesibil(int x, int y, int map[102][102]){
    if (x >= 1 && x <= n && y >= 1 && y <= m){
        if (map[x][y] == 0)
            return 1;
        else if (map[x][y] == -3 && map[x][y] == -2)
            return 1;
        else 
            return 0;
    } else
        return 0;
}

int main()
{
    queue <pair<int,int>> qr;
    queue <pair<int,int>> qj;
    int ri, rj, ji ,jj;
    fin>>n>>m;
    char sir[102];
    int k=0;
    fin.getline(sir,102);
    for (int i=1; i<=n; i++){
        fin.getline(sir, 102);
        k = 0;
        while (sir[k] != '\0'){
            if (sir[k] == ' '){
                map_romeo[i][k+1] = 0;
                map_juliet[i][k+1] = 0;
            }
            if (sir[k] == 'R'){
                map_romeo[i][k+1] = -2;
                map_juliet[i][k+1] = -2;
                ri = i;
                rj = k+1;
            } 
            if (sir[k] == 'J'){
                map_romeo[i][k+1] = -3;
                map_juliet[i][k+1] = -3;
                ji = i;
                jj = k+1;
            }
            if (sir[k] == 'X'){
                map_romeo[i][k+1] = -1;
                map_juliet[i][k+1] = -1;
            }
            k++;
        }
    }
    
    qr.push(make_pair(ri, rj));
    qj.push(make_pair(ji,jj));
    while (!qr.empty() || !qj.empty()){
        int iactr, jactr, iactj, jactj, ivecinr, jvecinr, ivecinj, jvecinj;
        if (!qr.empty()){
            iactr = qr.front().first;
            jactr = qr.front().second;
        }
        if (!qj.empty()){
            iactj = qj.front().first;
            jactj = qj.front().second;
        }
        for (int k=0; k<4; k++){
            if (!qr.empty()){
                ivecinr = dir_i[k] + iactr;
                jvecinr = dir_j[k] + jactr;
                if (accesibil(ivecinr, jvecinr, map_romeo)){
                    if (map_romeo[iactr][jactr] == -2)
                        map_romeo[ivecinr][jvecinr] = 1;
                    else
                        map_romeo[ivecinr][jvecinr] = map_romeo[iactr][jactr]+1;
                    qr.push(make_pair(ivecinr,jvecinr));                    
                }
            }
            if (!qj.empty()){
                ivecinj = dir_i[k] + iactj;
                jvecinj = dir_j[k] + jactj;
                if (accesibil(ivecinj, jvecinj, map_juliet)){
                    if (map_juliet[iactj][jactj] == -3)
                        map_juliet[ivecinj][jvecinj] = 1;
                    else
                        map_juliet[ivecinj][jvecinj] = map_juliet[iactj][jactj]+1;
                    qj.push(make_pair(ivecinj,jvecinj));                    
                }
            }
        }
        if (!qr.empty())
            qr.pop();
        if (!qj.empty())
            qj.pop();
    }
    
    int min=-1, minx, miny;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            if (map_romeo[i][j] != -1 && map_romeo[i][j] != -2 && map_romeo[i][j] != -3 && map_romeo[i][j] != 0){
                if (map_romeo[i][j] == map_juliet[i][j]){
                    if (min == -1){
                        min = map_romeo[i][j];
                        minx = i;
                        miny = j;
                    } else if (map_romeo[i][j] < min){
                        min = map_romeo[i][j];
                        minx = i;
                        miny = j;
                    }
                }
            }
        }
    }
    fout<<min<<" "<<minx<<" "<<miny;

    return 0;
}