Cod sursa(job #129919)

Utilizator MirageRobert Sandu Mirage Data 30 ianuarie 2008 16:47:04
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include<stdio.h>  
const int dl[]={-1,-1,0,1,1,1,0,-1};  
const int dc[]={0,1,1,1,0,-1,-1,-1};  
struct cod{  
int x,y;  
};  
cod coada[21000],cost[105][105];  
int nr[200][200],apar[200][200];  
char linie[110];  
int main(){  
freopen("rj.in","r",stdin);  
freopen("rj.out","w",stdout);  
int n,m,i,j,x1,x2,y1,y2,p,u,x,y,tmin=100000000;  
scanf("%d%d",&n,&m);  
fgets(linie,110,stdin);  
for(i=1;i<=n;++i){  
 fgets(linie,110,stdin);  
for(j=0;j<m;++j){  
if(linie[j]=='X')  
nr[i][j+1]=1;  
             if(linie[j]=='R'){  
                x1=i;  
                y1=j+1;  
              apar[x1][y1]=1;  
            }  
            if(linie[j]=='J'){  
                x2=i;  
              y2=j+1;  
            }  
        }  
     }  
  for(i=0;i<=m+1;++i)  
        nr[0][i]=nr[n+1][i]=1;  
     for(i=0;i<=n+1;++i)  
         nr[i][0]=nr[i][m+1]=1;  
     coada[0].x=x1;  
    coada[0].y=y1;  
     p=0;  
     u=1;  
     cost[x1][y1].x=1;  
    while(p!=u){  
        for(i=0;i<8;++i){  
           if(nr[coada[p].x+dl[i]][coada[p].y+dc[i]]==0 && apar[coada[p].x+dl[i]][coada[p].y+dc[i]]==0){  
              coada[u].x=coada[p].x+dl[i];  
             coada[u].y=coada[p].y+dc[i];  
                cost[coada[u].x][coada[u].y].x=cost[coada[p].x][coada[p].y].x+1;  
                apar[coada[u].x][coada[u].y]=1;  
                ++u;  
            }  
        }  
      ++p;  
     }  
     coada[0].x=x2;  
     coada[0].y=y2;  
      p=0;  
     u=1;  
      cost[x2][y2].y=1;  
      while(p!=u){  
          for(i=0;i<8;++i){  
              if(nr[coada[p].x+dl[i]][coada[p].y+dc[i]]==0 && apar[coada[p].x+dl[i]][coada[p].y+dc[i]]!=2){  
                  coada[u].x=coada[p].x+dl[i];  
                 coada[u].y=coada[p].y+dc[i];  
                  cost[coada[u].x][coada[u].y].y=cost[coada[p].x][coada[p].y].y+1;  
                  apar[coada[u].x][coada[u].y]=2;  
                 ++u;  
             }  
        }  
         ++p;  
     }  
        
    for(i=1;i<=n;++i){  
         for(j=1;j<=m;++j){  
             if(nr[i][j]==0){  
                 if((i!=x1 && j!=y1) || (i!=x2 && j!=y2)){  
                      if(cost[i][j].x>0 || cost[i][j].y>0){  
                       if(cost[i][j].x==cost[i][j].y){  
                             if(tmin>cost[i][j].y){  
                                  tmin=cost[i][j].x;  
                                x=i;  
                                y=j;  
                             }  
                         }  
                     }  
                 }  
             }  
        }  
     }  
	printf("%d %d %d\n",tmin,x,y);  
     return 0;  
}