Cod sursa(job #210519)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 27 septembrie 2008 22:18:42
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <queue>

using namespace std;
int n,m,a[101][101],b[101][101];
int r1,r2,j1,j2;

const int xx[]={-1,-1,-1,0,0,1,1,1},
          yy[]={-1,0,1,-1,1,-1,0,1};

void citire()
{
   char x[101];
   scanf("%d %d ",&n,&m);
   for(int i=1;i<=n;i++){
       fgets(x,m+1,stdin);
       for(int j=0;j<m;j++){
         if(x[j]==' ')
             {a[i][j+1]=0;b[i][j+1]=0;}
         if(x[j]=='R'){
              r1=i;
              r2=j+1;
              }
         if(x[j]=='J'){
              j1=i;
              j2=j+1;
               }
         if(x[j]=='X')
               {a[i][j+1]=-1;b[i][j+1]=-1;}
         }
       fgets(x,m+1,stdin);
       }
}

void solve()
{
    queue <int> c1,c2;
    int i,j,_i,_j;
    c1.push(r1);
    c2.push(r2);
    a[j1][j2]=-1;
    while(!c1.empty())
     {
      i=c1.front();
      j=c2.front();
      for(int k=0;k<8;k++)
       {
        _i=i+xx[k];
        _j=j+yy[k];

        if(_i<1||_i>n) continue;
        if(_j<1||_j>m) continue;
        if(a[_i][_j]!=0) continue;

        c1.push(_i);
        c2.push(_j);
        a[_i][_j]=a[i][j]+1;

       }
      c1.pop();
      c2.pop();
      a[r1][r2]=-1;
      }
    int min=100000,poz1,poz2;
    c1.push(j1);
    c2.push(j2);
    b[r1][r2]=-1;
    b[j1][j2]=0;
    while(!c1.empty())
     {
      i=c1.front();
      j=c2.front();
      for(int k=0;k<8;k++)
       {
        _i=i+xx[k];
        _j=j+yy[k];

        if(_i<1||_i>n) continue;
        if(_j<1||_j>m) continue;
        if(b[_i][_j]!=0) continue;

        c1.push(_i);
        c2.push(_j);
        b[_i][_j]=b[i][j]+1;
        if(b[_i][_j]==a[_i][_j])
           if(b[_i][_j]<min)
             {min=b[_i][j];
              poz1=_i;
              poz2=_j;
             }
       }
      c1.pop();
      c2.pop();
      b[j1][j2]=-1;
      }

 printf("%d %d %d",min+1,poz1,poz2);


}

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    citire();
    solve();
    return 0;
}