Cod sursa(job #446256)

Utilizator bog29Antohi Bogdan bog29 Data 25 aprilie 2010 15:40:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
#include<queue>
#define dmax 105
using namespace std;

short int n,m,mat[dmax][dmax],sol[2][dmax][dmax],x,y,xx,yy,mn=-1,p1,p2;
const int dx[]={-1,-1,0,1,1,1, 0, -1};
const int dy[]={0 ,1, 1,1,0,-1,-1,-1};

struct poz
{	short int x;
	short int y;
};

queue<struct poz>q;

int bune(short int i,short int j)
{	return (i>0 && i<=n && j>0 && j<=m);
}

void lee(int p,int r,int nr)
{	int	ii,jj,k;
	poz w,crt;
	q.empty();
	w.x=p;
	w.y=r;
	sol[nr][p][r]=1;
	q.push(w);
	while(!q.empty() )
	{	crt=q.front();
		q.pop();
		for(k=0;k<8;k++)
		{	ii=crt.x+dx[k];
			jj=crt.y+dy[k];
			if(bune(ii,jj) )
				if(mat[ii][jj]!=1)
					if(!sol[nr][ii][jj] )
					{	sol[nr][ii][jj]	= sol[nr][crt.x][crt.y] +1;
						w.x=ii;
						w.y=jj;
						q.push(w);
					}
		}		
	}
}

	
int main()
{	FILE *f=fopen("rj.in","r");
	FILE *g=fopen("rj.out","w");
	int i,j;
	char c;
	fscanf(f,"%d %d\n",&n,&m);
	for(i=1;i<=n;i++)
	{	fscanf(f,"%c",&c);
		for(j=1;j<=m;j++)
		{	if(c=='X')
				mat[i][j]=1;
			else if(c=='R')
			{	x=i;
				y=j;
			}
			else if(c=='J')
			{	xx=i;
				yy=j;
			}
			else if(c==' ')mat[i][j]=0;
			fscanf(f,"%c",&c);
		}
	}	
	fclose(f);
	lee(x,y,0);
	lee(xx,yy,1);
	for(i=1;i<=n;i++)
	{	for(j=1;j<=m;j++)
			if(mat[i][j]!=1 && sol[0][i][j] && sol[1][i][j])
				if(sol[0][i][j]==sol[1][i][j])
					if(sol[0][i][j] < mn || mn==-1)
					{	mn=	sol[0][i][j];
						p1=i;
						p2=j;
					}	
	}	
	fprintf(g,"%d %d %d",mn,p1,p2); 
	fclose(g);
	return 0;
}