Cod sursa(job #2494984)

Utilizator FastmateiMatei Mocanu Fastmatei Data 18 noiembrie 2019 18:57:16
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <bits/stdc++.h>
#define oo 5555555
using namespace std;

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

int n,m,xr,yr,xj,yj;
char a[105][105];
int dr[105][105];
int dj[105][105];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
queue<pair<int,int> > q;
void Citire()
{
    int i,j;
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
        fin.getline(a[i]+1,103);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            {
                if(a[i][j]=='R') {xr=i;yr=j;}
                else if(a[i][j]=='J') {xj=i;yj=j;}
            }
}

bool Inside(int i,int j)
{
    return (i>=1 && i<=n && j>=1 && j<=m);
}

void Lee(char P)
{
    int i,j,x,y,k;
    if(P=='R')
    {
        q.push({xr,yr});
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                dr[i][j]=oo;
        dr[xr][yr]=0;
        while(!q.empty())
        {
            i=q.front().first;
            j=q.front().second;
            q.pop();
            for(k=0;k<4;k++)
            {
                x=i+dx[k];
                y=j+dy[k];
                if(Inside(x,y) && dr[x][y]>dr[i][j]+1 && a[i][j]!='X')
                {
                    dr[x][y]=dr[i][j]+1;
                    q.push({x,y});
                }
            }
        }
    }
    else
    {
        q.push({xj,yj});
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                dj[i][j]=oo;
        dj[xj][yj]=0;
        while(!q.empty())
        {
            i=q.front().first;
            j=q.front().second;
            q.pop();
            for(k=0;k<4;k++)
            {
                x=i+dx[k];
                y=j+dy[k];
                if(Inside(x,y) && dj[x][y]>dj[i][j]+1 && a[i][j]!='X')
                {
                    dj[x][y]=dj[i][j]+1;
                    q.push({x,y});
                }
            }
        }
    }
}

void Caut()
{
    int i,j,tmin=1e9,x,y;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(dr[i][j]==dj[i][j] && dr[i][j]!=0)
            {
                if(tmin>dr[i][j])
                {
                    tmin=dr[i][j];
                    x=i;
                    y=j;
                }
            }
    fout<<tmin<<" "<<x<<" "<<y<<"\n";
    fout.close();
}

int main()
{
    Citire();
    Lee('R');
    Lee('J');
    Caut();
    return 0;
}