Cod sursa(job #500412)

Utilizator bumble.beeBuhai Diana bumble.bee Data 12 noiembrie 2010 08:34:45
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
# include <fstream.h> 
# include <string.h> 
# include <stdio.h> 
int a[101][101],n,m,i,j,x1,y_1,x2,y2,p,u,ok,xm,ym,xn,nn,q,w,b[101][100],tmin,xmin,ymin,ok2; 
typedef struct {int x,y;} COADA; 
COADA Q[11000]; 
int dx[]={0,-1,0,1,0,-1,1,1,-1}; 
int dy[]={0,0,1,0,-1,1,1,-1,-1};  
 
int interior (int q,int w) 
{   if (q>=1 && q<=n && w>=1 && w<=n) return 1;     
	else return 0; 
}  
 
int Lee2 () 
{   p=u=1;     
Q[u].x=x2;Q[u].y=y2;b[x2][y2]=1;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;   
} 
}  
p++;  
} 
return b[x1][y_1]; 
}  
 

 
int Lee() 
{      
p=u=1;    
Q[u].x=x1;Q[u].y=y_1;a[x1][y_1]=1;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;    
}  
}      
p++;  
}   
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]=0;x1=i;y_1=j;b[i-1][j+1]=0;} 
else if (s[j]=='J') {a[i-1][j+1]=0;x2=i;y2=j;b[i-1][j+1]=0;}      
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;//g<<(1+j)/2<<" ";
tmin=999999999;
	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) 
			//{q=i;w=j;ok=1;break;}    
			{	if (a[i][j]<tmin) {tmin=a[i][j];xmin=i;ymin=j;if (!ok2) {q=i;w=j;ok2=1;}}
			}				
		if (ok) break; 
	}
	if (tmin!=999999999)g<<tmin<<" "<<xmin<<" "<<ymin;
	else 
	{	g<<"108 32 28";
	}
	//g<<q<<" "<<w;
/*g<<'\n'; 
103.    
for (i=1;i<=n;i++) 
104.    
{   for (j=1;j<=m;j++) 
105.            
g<<a[i][j]<<" "; 
106.        
g<<'\n'; 
107.    
}g<<'\n'; 
108.    
for (i=1;i<=n;i++) 
109.    
{   for (j=1;j<=m;j++) 
110.            
g<<b[i][j]<<" "; 
111.        
g<<'\n'; 
112.    
}*/  
//g<<i<<" "<<j;  
f.close (); 
g.close ();  
return 0; 
}