Cod sursa(job #2712290)

Utilizator StefanSVStefan S V StefanSV Data 25 februarie 2021 16:24:50
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <queue>

using namespace std;

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

int n,m,mat[101][101],di[]={-1,-1,-1,0,0,1,1,1},dj[]={-1,0,1,-1,1,-1,0,1};
int vizr[101][101],vizj[101][101];

int main()
{
    int ri,rj,ji,jj;
    in>>n>>m>>ws;
    for(int i=0 ; i<n ; i++)
    {
        char a[101];
        in.getline(a,101);
        for(int j=0 ; j<m ; j++)
        {
            if(a[j]==' ')
                mat[i][j]=1;
            else if(a[j]=='R')
                {mat[i][j]=2; ri=i;rj=j;}
            else if(a[j]=='J')
                {mat[i][j]=3; ji=i;jj=j;}
        }
    }
    queue <int> qi,qj;
    vizr[ri][rj]=1;
    qi.push(ri);
    qj.push(rj);
    while(!qi.empty())
    {
        int i=qi.front(),j=qj.front();
        for(int k=0 ; k<8 ; k++)
        {
            int ii=i+di[k],jj=j+dj[k];
            if(ii>=0 && jj>=0 && ii<n && jj<m && mat[ii][jj]!=0 && vizr[ii][jj]==0)
            {
                vizr[ii][jj]=vizr[i][j]+1;
                qi.push(ii);
                qj.push(jj);
            }
        }
        qi.pop();
        qj.pop();
    }
    vizj[ji][jj]=1;
    qi.push(ji);
    qj.push(jj);
    while(!qi.empty())
    {
        int i=qi.front(),j=qj.front();
        for(int k=0 ; k<8 ; k++)
        {
            int ii=i+di[k],jj=j+dj[k];
            if(ii>=0 && jj>=0 && ii<n && jj<m && mat[ii][jj]!=0 && vizj[ii][jj]==0)
            {
                vizj[ii][jj]=vizj[i][j]+1;
                qi.push(ii);
                qj.push(jj);
            }
        }
        qi.pop();
        qj.pop();
    }
    int min=100000,iii,jjj;
    for(int i=0 ; i<n ; i++)
        for(int j=0 ; j<m ; j++)
            if(vizj[i][j]==vizr[i][j] && vizj[i][j]<min && vizj[i][j]>0)
            {
                min=vizj[i][j];
                iii=i;
                jjj=j;
            }
    out<<min<<" "<<iii+1<<" "<<jjj+1;
    return 0;
}