Cod sursa(job #735174)

Utilizator FayedStratulat Alexandru Fayed Data 15 aprilie 2012 20:12:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<fstream>
using namespace std;

int A[110][110],B[110][110];
int n,m;
int xr,yr,xj,yj;
int V[8] = {0,0,1,1,1,-1,-1,-1};
int C[8] = {1,-1,0,1,-1,0,1,-1};

struct coord{
          int x,y;

       }q[10001];

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

int main()
{

   f>>n>>m;
int cx = 0,cy = 0,tmax = 1000000;
f.get();
char s[110];
int i,j;
   for(i = 1;i<=n;++i)
{
    f.getline(s,110);
       for(j = 0;j<m;++j)
     {
           if(s[j] ==' ')
         {

         A[i][j+1] = 0;
         B[i][j+1] = 0;
           }
       else if(s[j] == 'X')
         {
           A[i][j+1] = -1;
           B[i][j+1] = -1;
     }
      else if(s[j] == 'R')
       {
        xr = i; yr = j+1;
     }
    else {
           xj = i; yj = j+1;
           }
    }
}
f.close();

for(int i = 0;i<=n+1;++i)
 A[i][0] = B[i][0] = A[i][n+1] = B[i][n+1] = -1;

   for(int i = 0;i<=m+1;++i)
 A[0][i] = B[0][i] = A[n+1][i] = B[n+1][i] = -1;

int x,y,k,ul = 0,pr = 0;

A[xr][yr] = 1;
    q[ul].x = xr;
    q[ul].y = yr;

 while(pr <= ul)
  {
      x = q[pr].x;
      y = q[pr].y;
 ++pr;
  for(k = 0;k<8;++k)
   {
       i = x+V[k];
       j = y+C[k];
     if(A[i][j] == 0)
    {
        ++ul;
     q[ul].x = i;
      q[ul].y =j;
        A[i][j] = A[x][y] + 1;
    }
   }
  }


   int ul1 = 0;
  int pr1 = 0;
  B[xj][yj] = 1;
  q[ul1].x = xj;
  q[ul1].y = yj;

 while(pr1 <= ul1)
  {
      x = q[pr1].x;
      y = q[pr1].y;
  ++pr1;
  for(k = 0;k<8;++k)
   {
       i = x+V[k];
       j = y+C[k];
     if(B[i][j] == 0)
    {
        ++ul1;
     q[ul1].x = i;
      q[ul1].y =j;
        B[i][j] = B[x][y] + 1;
    }
   }

}

for(i = 1;i<=n;++i)
  {
      for(j = 1;j<=m;++j)
       if(A[i][j] == B[i][j] && A[i][j]>0)
          if(A[i][j]<tmax)
        {

             tmax = A[i][j];
             cx = i;
             cy = j;
               }
}

g<<tmax << " " << cx << " " <<cy;
g.close();


return 0;
}