Cod sursa(job #445210)

Utilizator Anamaria20Cotirlea Anamaria Anamaria20 Data 23 aprilie 2010 08:40:18
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <stdio.h>
#include <queue>

using namespace std; 

FILE *f,*s;  
 
int m,n,i,j,xr,yr,xj,yj,a,b,c,v1[150][150],v4[150][150];  
 
char ch;  
 
struct punct 
{ 
    
	int x; 
	int y; 
}; 
   
queue <punct> v2;   
 
punct p1,p2,v3[10]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; 

void Lee1(int x1, int y1) 
{     
	p1.x=x1; 
	p1.y=y1; 
    
	v2.push(p1); 
    
	p2=p1; 
	while(v2.size()) 
	{ 
		p1=v2.front(); 
        
		v2.pop(); 
 
		p2=p1; 
		for(i=0;i<=7;i++) 
		{ 
			p1=p2; 
            
			p1.x+=v3[i].x; 
			p1.y+=v3[i].y; 
              
			if(p1.x>=1&&p1.x<=m&&p1.y>=1&&p1.y<=n&&v1[p1.x][p1.y]>=0&&((v1[p1.x-v3[i].x][p1.y-v3[i].y]+1)<v1[p1.x][p1.y] || v1[p1.x][p1.y]==0)) 
			{ 
				v2.push(p1); 
                
				v1[p1.x][p1.y]=v1[p1.x-v3[i].x][p1.y-v3[i].y]+1; 
			}   
		}   
	}   
} 

void Lee2(int x1, int y1) 
{     
	p1.x=x1; 
	p1.y=y1; 
    
	v2.push(p1); 
    
	p2=p1; 
	while(v2.size()) 
	{ 
		p1=v2.front(); 
        
		v2.pop(); 
 
		p2=p1; 
		for(i=0;i<=7;i++) 
		{ 
			p1=p2; 
            
			p1.x+=v3[i].x; 
			p1.y+=v3[i].y; 
              
			if(p1.x>=1&&p1.x<=m&&p1.y>=1&&p1.y<=n&&v4[p1.x][p1.y]>=0&&((v4[p1.x-v3[i].x][p1.y-v3[i].y]+1)<v4[p1.x][p1.y] || v4[p1.x][p1.y]==0)) 
			{ 
				v2.push(p1); 
                
				v4[p1.x][p1.y]=v4[p1.x-v3[i].x][p1.y-v3[i].y]+1; 
			}   
		}   
	}   
} 


int main() 
{     
	f=fopen("rj.in","r"); 
	s=fopen("rj.out","w"); 
    
	fscanf(f,"%d %d\n",&m,&n); 
    
	for(i=1;i<=m;i++) 
	{ 
		for(j=1;j<=n;j++) 
		{    
			fscanf(f,"%c",&ch); 
           
			if(ch=='X') 
				v1[i][j]=-1; 
             
				if(ch==' ') 
					v1[i][j]=0; 
             
				if(ch=='R') 
				{ 
					v1[i][j]=0; 
                 
					xr=i; 
					yr=j; 
				}    
             
				if(ch=='J') 
				{ 
					v1[i][j]=0; 
                
					xj=i; 
					yj=j; 
				}    
			
			v4[i][j]=v1[i][j]; 
		}    
		fscanf(f,"%c",&ch); 
	}    

	Lee1(xr,yr); 
    
	Lee2(xj,yj); 

	a=10000; 

	for(i=1;i<=m;i++) 
	{ 
		for(j=1;j<=n;j++) 
		{ 
			if(v1[i][j]>0 && v1[i][j]==v4[i][j] && v1[i][j]<a) 
			{ 
				a=v1[i][j]; 
                
				b=i; 
				c=j; 
			}	    
		}    
	}    

	fprintf(s,"%d %d %d",a+1,b,c); 

	fclose(s);

	return 0;	
}