Cod sursa(job #3185309)

Utilizator IustaganIusin Dabu Iustagan Data 18 decembrie 2023 18:16:02
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
struct crd{int x,y;}vecin,r,juliet;
int vr[102][102],vj[102][102];

const int dl[]={-1,-1,-1,0,1,1,1,0};
const int dc[]={-1,0,1,1,1,0,-1,-1};
int incr=0,sfr=0;
int incj=0,sfj=0;
long long int min1=10000000;
int x,y;

queue<crd> q;


void LEE1(int vr[][102],crd r,crd vecin)
{
     q.push(r);
     vr[r.x][r.y]=1;
     crd pcrt;
     while(!q.empty())
     {
          pcrt=q.front();
          q.pop();
          for(int i=0;i<8;i++)
          {
               vecin.x=pcrt.x+dl[i];
               vecin.y=pcrt.y+dc[i];
               if(vr[vecin.x][vecin.y]==0)
               {
                    vr[vecin.x][vecin.y]=vr[pcrt.x][pcrt.y]+1;
                    q.push(vecin);
               }
          }
     }
}

void LEE2(int vj[][102],crd juliet,crd vecin)
{
     q.push(juliet);
     vj[juliet.x][juliet.y]=1;
     crd pcrt;
     while(!q.empty())
     {
          pcrt=q.front();
          q.pop();
          for(int i=0;i<8;i++)
          {
               vecin.x=pcrt.x+dl[i];
               vecin.y=pcrt.y+dc[i];
               if(vj[vecin.x][vecin.y]==0)
               {
                    vj[vecin.x][vecin.y]=vj[pcrt.x][pcrt.y]+1;
                    q.push(vecin);
               }
          }
     }
}

int main()
{
     int n,m;
     string d;
     cin>>n>>m;
     cin.get();
     for(int i=1;i<=n;i++)
     {
          getline(cin,d);

          for(int j=0;j<m;j++)
          if(d[j]=='R')
          {
               r.x=i;
               r.y=j+1;
          }
          else if(d[j]=='J')
          {
               juliet.x=i;
               juliet.y=j+1;
          }
          else if(d[j]=='X')
          {
               vr[i][j+1]=-1;
               vj[i][j+1]=-1;
          }
     }

     for(int i=0;i<=n+1;i++)
     {
          vr[i][0]=-1;
          vr[i][m+1]=-1;
          vj[i][0]=-1;
          vj[i][m+1]=-1;
     }
     for(int i=0;i<=m+1;i++)
     {
          vr[0][i]=-1;
          vr[n+1][i]=-1;
          vj[0][i]=-1;
          vj[n+1][i]=-1;
     }

     LEE1(vr,r,vecin);
     LEE2(vj,juliet,vecin);

     for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     if(vr[i][j]==vj[i][j])
     {
          if(min1>vr[i][j]&&vr[i][j]>0)
          {
               min1=vr[i][j];
               x=i;
               y=j;
          }
     }
     cout<<min1<<' '<<x<<' '<<y;
}