Cod sursa(job #503953)

Utilizator r0cesStefan Radu r0ces Data 25 noiembrie 2010 21:18:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<fstream.h>
#include<math.h>
#include<iostream.h>
#include<stdio.h>
typedef struct{
    int x,y;}COADA;
COADA c[1100];
int a[150][150],b[150][150];
int p,u,xv,yv,xn,x1,x2,y2,n,m,i,j,z,t,timp,ok,min,li,co;
    int nn,yy;
    int dx[]={0,-1,-1,0,1,1,1,0,-1};  
	int dy[]={0,0,1,1,1,0,-1,-1,-1}; 
    char car[120];
int main()
{
    
    ifstream fcin("rj.in");
    ofstream fcout("rj.out");
	fcin>>n>>m;  
	for (i=1;i<=n+1;i++)  
	{  
		fcin.getline(car,101);   
		if (i!=1){    
		for (j=0;j<=m;j++)          
		if (car[j]==' ') a[i-1][j+1]=a[i-1][j+1]=0;          
		else if (car[j]=='R') {a[i-1][j+1]=-2;x1=i-1;yy=j+1;b[i-1][j+1]=-2;}  
		else if (car[j]=='J') {a[i-1][j+1]=-3;x2=i-1;y2=j+1;b[i-1][j+1]=-3;}       
		else if (car[j]=='X') {a[i-1][j+1]=-1;b[i-1][j+1]=-1;}  
		}    
	}    
    

	p=u=1;     
	c[u].x=x1;c[u].y=yy;a[x1][yy]=0;ok=0;    
	while (p<=u && ok==0)  
	{   
		xv=c[p].x;yv=c[p++].y;       
		for (i=1;i<=8;i++)      
		{  
			xn=xv+dx[i];     
			nn=yv+dy[i];        
			if (xn>=1&&xn<=n&&nn>=1&&nn<=m&&a[xn][nn]==0)           
			{  
				a[xn][nn]=a[xv][yv]+1;            
				c[++u].x=xn;c[u].y=nn;             
				if (xn==x2 && nn==y2) ok=1;     
			}   
		}       
    }    
     
    
     
    p=u=1;      
	c[u].x=x2;c[u].y=y2;b[x2][y2]=0;ok=0;    
	while (p<=u && ok==0)     
	{   
		xv=c[p].x;yv=c[p++].y;       
		for (i=1;i<=8;i++)      
		{  
			xn=xv+dx[i];       
			nn=yv+dy[i];      
			if (xn>=1&&xn<=n&&nn>=1&&nn<=m&&b[xn][nn]==0)       
		{  
			b[xn][nn]=b[xv][yv]+1;                
			c[++u].x=xn;c[u].y=nn;               
			if (xn==x1 && nn==yy) ok=1;    
		}  
	}   
}  
     
     
    min=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<min) {min=a[i][j]+1;z=i;t=j;} 
                    else if (a[i][j]==min && z>=i) {z=i;t=j;}   
	}    
             
     
    fcout<<min<<" "<<z<<" "<<t;
	fcin.close ();  
	fcout.close ();   
    return 0;
}