Cod sursa(job #316751)

Utilizator klamathixMihai Calancea klamathix Data 20 mai 2009 23:39:53
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include<cstdio>
#include<queue>

#define MAXN 105
#define INFINIT 100000

using namespace std;

int i , j , k , N , M , A[MAXN][MAXN] ,x1 , x2 , y1 , y2 , B[MAXN][MAXN] , maxs =  1000000, ind1 , ind2;
char c[MAXN];
int vert[10] = { -1 , 1 , 0 , 0 , -1 , 1 , -1 , 1};
int oriz[10] = { 0, 0 ,  -1 , 1 ,  1 , 1, -1 ,-1};

struct coord {
       int x;
       int y;
       };

queue <coord> Q;

inline int ok( int ii , int jj )
{
       if( ii >= 1 && ii <= N && jj >= 1 && jj <= M)
       //if(A[ii][jj] != -1);
       return 1;

return 0;
}
 

coord  start , end , aux , X;

void read()
{
     for( i = 1 ; i <= N ; i++)
          {
              fgets(c,MAXN ,stdin);
              for( j = 0 ; j < M ; j++)
              {
                   //A[i][j + 1] = INFINIT;
                   
                   if( c[j] == 'X' ) A[i][j + 1] = B[i][j + 1] =  -1;
                   if(c[j] == 'R' ) start.x = i , start.y = j + 1;
                   else if( c[j]== 'J') end.x = i, end.y = j + 1;
              }
          scanf("\n");
          }
}

void BFS(coord start , int A[MAXN][MAXN])
{
     Q.push(start) ;
     
     while(!Q.empty())
     {
                      X = Q.front() , Q.pop();
                      
                      for( i = 0 ; i <= 7 ; ++i)
                      {
                           aux.x = X.x + vert[i];
                           aux.y = X.y + oriz[i];
                           
                           if(ok(aux.x , aux.y))
                                       if( !A[aux.x][aux.y])
                                           {
                                                            A[aux.x][aux.y] = A[X.x][X.y] + 1;
                                                            Q.push(aux);
                                           }
                      }
     }

}

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    
    scanf("%d %d\n",&N,&M);
    
    read();
    
    A[start.x][start.y] = 1;
    B[end.x][end.y] = 1;
    
  //  printf("%d %d\n",end.x ,end.y);
    
    BFS(start , A) , BFS(end , B);
    
    for( i = 1 ; i <= N ; i++)   
         for( j = 1 ; j <= M ; j++)
              if( A[i][j] == B[i][j] && A[i][j] != - 1 && A[i][j] != 0)
                  if ( A[i][j] < maxs )  maxs = A[i][j] , ind1 = i , ind2 = j;
    
    printf("%d %d %d" , maxs , ind1 , ind2);
return 0;
}