Cod sursa(job #1349045)

Utilizator asavoaeigeoAsavoaei Georgiana asavoaeigeo Data 19 februarie 2015 22:57:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

int R[102][102],J[102][102],tmin=999999;
char s[102];
struct lee
{int a,b;};

queue<lee>Q;
int col[8]={0,1,1,1,0,-1,-1,-1},lin[8]={-1,-1,0,1,1,1,0,-1};

inline void drumR(int x1,int y1,int x2,int y2,int n,int m)
{
    lee pas;
    int i,j;
    pas.a=x1;pas.b=y1;R[x1][y1]=1;
    Q.push(pas);
    while(Q.size())
    { i=Q.front().a;
      j=Q.front().b;
      int z;
      for(z=0;z<8;z++)
      {
      if(R[i+lin[z]][j+col[z]]==0 &&i+lin[z]<=n && i+lin[z]>=1 &&j+col[z]>=1 &&j+col[z]<=m)
         { pas.a=i+lin[z];
           pas.b=j+col[z];
          R[i+lin[z]][j+col[z]]=R[i][j]+1;
          Q.push(pas);
         }
      }
    Q.pop();
    }
}

inline void drumJ(int x1,int y1,int x2,int y2,int n,int m)
{
    lee pas;
    int i,j;
    pas.a=x1;pas.b=y1;J[x1][y1]=1;
    Q.push(pas);
    while(Q.size())
    { i=Q.front().a;
      j=Q.front().b;
      int z;
      for(z=0;z<8;z++)
      {
      if(J[i+lin[z]][j+col[z]]==0 &&i+lin[z]<=n && i+lin[z]>=1 &&j+col[z]>=1 &&j+col[z]<=m)
         { pas.a=i+lin[z];
           pas.b=j+col[z];
          J[i+lin[z]][j+col[z]]=J[i][j]+1;
          Q.push(pas);
         }

     }
    Q.pop();
   }
}

int main()
{
    int n,m,i=1,j,x1,x2,y1,y2;
    fin>>n>>m;
    fin.get();
   for(i=1;i<=n;i++)
    {
     fin.getline(s,m+1);
     for(j=1;j<=m;j++)
        {if(s[j-1]==' ') R[i][j]=J[i][j]=0;
         else if(s[j-1]=='X') R[i][j]=J[i][j]=-1;
        if(s[j-1]=='R') {x1=i;y1=j;}
        if(s[j-1]=='J') { x2=i;y2=j;}
        }
    }


    drumR(x1,y1,x2,y2,n,m);
    drumJ(x2,y2,x1,y1,n,m);

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
          if(R[i][j]>1&&J[i][j]>1)
                { if(R[i][j]==J[i][j]&&R[i][j]<tmin)
                          {tmin=R[i][j];x1=i;y1=j;}
                }
    }
    fout<<tmin<<" "<<x1<<" "<<y1;
    return 0;
}