Cod sursa(job #2721755)

Utilizator Albert_GAlbert G Albert_G Data 12 martie 2021 10:48:01
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <queue>

using namespace std;

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

int dl[] = {-1, 0, 0, 1, -1, -1, 1, 1};
int dc[] = {0, -1, 1, 0, -1, 1, -1, 1};
const int N = 102;
int distR[N][N],distJ[N][N],n,m;
bool obs[N][N];
struct pos{
    int l,c;
}romeo,juliet;
queue <pos> q;

void lee(pos pers, int dist[N][N]){
     dist[pers.l][pers.c] = 1;
     q.push(pers);
     while(!q.empty()){
        pos root = q.front();
        q.pop();
        for(int i=0;i<8;++i)
        {
            int new_l = root.l + dl[i], new_c = root.c + dc[i];
            if(!obs[new_l][new_c] && dist[new_l][new_c]==0)
            {
                dist[new_l][new_c] = dist[root.l][root.c] + 1 ;
                q.push({new_l,new_c});
            }
        }
     }
}

void bordare()
{
    for(int i=0;i<=n+1;++i){
        obs[i][0] = obs[i][m+1] = 1;
    }
    for(int i=0;i<=m+1;++i){
        obs[0][i] = obs[n+1][i] = 1;
    }
}

int main()
{
    in>>n>>m;
    in.ignore(1);
    for(int i=0;i<n;++i)
    {
        char line[101];
        in.getline(line,N);
        for(int j=0;j<m;++j)
        {
            switch(line[j]){
            case 'R':
                {
                    romeo = {i+1,j+1};
                    break;
                }
            case 'J':
                {
                    juliet = {i+1,j+1};
                    break;
                }
            case 'X':
                {
                    obs[i+1][j+1] = 1;
                }

            }
        }
    }
    bordare();
    lee(romeo,distR);
    lee(juliet,distJ);
    int minDist = N*N,imeet,jmeet;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(!obs[i][j] && distR[i][j]!=0 && distR[i][j] == distJ[i][j] && distJ[i][j]<minDist){
                minDist = distJ[i][j];
                imeet = i, jmeet = j;
            }
        }
    }
    out<<minDist<<' '<<imeet<<' '<<jmeet;
    return 0;
}