Cod sursa(job #2837569)

Utilizator daria0123daria ghitescu daria0123 Data 22 ianuarie 2022 11:49:48
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <iostream>
#include <queue>
#define MaxN 150
#define inf 1000000
using namespace std;

int n, m, xr,yr, xj,yj ;
char mat[MaxN][MaxN];
int distr[MaxN][MaxN];
int distj[MaxN][MaxN];
int dx[8]= {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8]= {0, 1, 1, 1, 0, -1, -1, -1};

bool verif(int x, int y)
{
    return 0<x&& x<=n && 0<y&&y<=m;

}

void leer()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            distr[i][j]=inf;
        }
    distr[xr][yr]=1;
    queue<pair<int, int>>q;
    q.push({xr, yr});
    while(!q.empty())
    {
        xr=q.front().first;
        yr=q.front().second;
        q.pop();
        for(int i=0; i<8; i++)
        {
            int xn=xr+dx[i];
            int yn=yr+dy[i];
            if(verif(xn, yn)&& mat[xn][yn]!='X'&& distr[xn][yn]>distr[xr][yr]+1)
            {
                distr[xn][yn]=1+distr[xr][yr];
                q.push({xn, yn});
            }
        }
    }
}

void leej()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            distj[i][j]=inf;
        }
    distj[xj][yj]=1;
    queue<pair<int, int>>q;
    q.push({xj, yj});
    while(!q.empty())
    {
        xj=q.front().first;
        yj=q.front().second;
        q.pop();
        for(int i=0; i<8; i++)
        {
            int xn=xj+dx[i];
            int yn=yj+dy[i];
            if(verif(xn, yn)&& mat[xn][yn]!='X'&& distj[xn][yn]>distj[xj][yj]+1)
            {
                distj[xn][yn]=1+distj[xj][yj];
                q.push({xn, yn});
            }
        }
    }
}

int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);

    cin >> n >> m;
    cin.getline(mat[0], 150); // scap de \n de la final
    for (int i = 1; i <= n; i++)
    {
        cin.getline(mat[i] + 1, 150);
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(mat[i][j]=='R')
            {
                xr=i;
                yr=j;
            }
            if(mat[i][j]=='J')
            {
                xj=i;
                yj=j;
            }
        }
    leej();
    leer();
    int minim=inf;
    int minx, miny;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            int maxim=max(distr[i][j], distj[i][j]);
            if(maxim<minim)
            {
                minim=maxim;
                minx=i;
                miny=j;
            }
        }
    }
    cout<<minim<<" "<<minx<<" "<<miny;

    return 0;
}