Cod sursa(job #503940)

Utilizator r0cesStefan Radu r0ces Data 25 noiembrie 2010 21:02:47
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 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;
            }
        }
    }
     
    
     
    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;
            }
        }
    }
     
     
    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;
}