Cod sursa(job #503939)

Utilizator r0cesStefan Radu r0ces Data 25 noiembrie 2010 21:02:37
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
# include <fstream.h>  
# include <string.h>  
# include <stdio.h>  
int a[150][150],n,m,i,j,x1,y_1,x2,y2,p,u,ok,xm,ym,xn,nn,q,w,b[150][150],tmin,xmin,ymin,ok2;  
typedef struct {int x,y;} COADA;  
COADA Q[11000];  
int dx[]={0,-1,-1,0,1,1,1,0,-1};  
int dy[]={0,0,1,1,1,0,-1,-1,-1};   
int interior (int q,int w)  
{   if (q>=1 && q<=n && w>=1 && w<=m) return 1;          
else return 0;  
}   
 
 
int Lee2 ()  
{   p=u=1;      
Q[u].x=x2;Q[u].y=y2;b[x2][y2]=0;ok=0;    
while (p<=u && ok==0)     
{   xm=Q[p].x;ym=Q[p++].y;       
for (i=1;i<=8;i++)      
{   xn=xm+dx[i];       
nn=ym+dy[i];      
if (interior (xn,nn)==1 && b[xn][nn]==0)       
{   b[xn][nn]=b[xm][ym]+1;                
Q[++u].x=xn;Q[u].y=nn;               
if (xn==x1 && nn==y_1) ok=1;    
}  
}   

}  
return b[x1][y_1];  
}    
 
  
 
int Lee()  
{       
p=u=1;     
Q[u].x=x1;Q[u].y=y_1;a[x1][y_1]=0;ok=0;    
while (p<=u && ok==0)  
{   xm=Q[p].x;ym=Q[p++].y;       
for (i=1;i<=8;i++)      
{   xn=xm+dx[i];     
nn=ym+dy[i];        
if (interior (xn,nn)==1 && a[xn][nn]==0)           
{   a[xn][nn]=a[xm][ym]+1;            
Q[++u].x=xn;Q[u].y=nn;             
if (xn==x2 && nn==y2) ok=1;     
}   
}       
  
}    
return a[x2][y2];  
}  
  
 
int main ()  
{   ifstream f("rj.in");    
ofstream g("rj.out");    
char s[101];  
f>>n>>m;  
for (i=1;i<=n+1;i++)  
{   f.getline(s,101);   
if (i!=1){    
for (j=0;j<=m;j++)          
if (s[j]==' ') a[i-1][j+1]=a[i-1][j+1]=0;          
else if (s[j]=='R') {a[i-1][j+1]=-2;x1=i;y_1=j;b[i-1][j+1]=-2;}  
else if (s[j]=='J') {a[i-1][j+1]=-3;x2=i;y2=j;b[i-1][j+1]=-3;}       
else if (s[j]=='X') {a[i-1][j+1]=-1;b[i-1][j+1]=-1;}  
}    
}    
x1=x1-1;y_1=y_1+1;   
x2=x2-1;y2=y2+1;  
i=Lee ();    
j=Lee2 ();ok=0;ok2=0;
tmin=100000; 
    
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]+1<tmin) {tmin=a[i][j]+1;xmin=i;ymin=j;} 
                    
else if (a[i][j]==tmin && xmin>=i) {xmin=i;ymin=j;}   
}    
g<<tmin<<" "<<xmin<<" "<<ymin; 
f.close();
g.close();
return 0;
}