Cod sursa(job #796749)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 12 octombrie 2012 14:25:52
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include<cstdio>

using namespace std;

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

struct coord{
int x,y;
}q[10001];



  void citesc()
{
    scanf("%d%d\n",&n,&m);

char s[110];
int i,j;
   for(i = 1;i<=n;++i)
{
    gets(s);
       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;
           }
    }
}}

 void bordez()
  {
   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;
  }

void leerom()
{

 int x,y,i,j,k,ul = 0,pr = 0;
A[xr][yr] = 2;
    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;
    }
   }

}}

void leejul()
{
   int ul = 0;
  int pr = 0;
  int i,j,x,y,k;
  B[xj][yj] = 2;
  q[ul].x = xj;
  q[ul].y = yj;

 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(B[i][j] == 0)
    {
        ++ul;
     q[ul].x = i;
      q[ul].y =j;
        B[i][j] = B[x][y] + 1;
    }
   }

}}

void afisez()
{
int i,j,cx = 0,cy = 0,tmax = 1000000;
for(i = 1;i<=n;++i)
  {
      for(j = 1;j<=m;++j)
       if(A[i][j] == B[i][j] && A[i][j]>1)
          if(A[i][j]-1<tmax)
        {

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

printf("%d %d %d",tmax,cx,cy);
}
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    citesc();
    bordez();
    leerom();
    leejul();
    afisez();
return 0;
}