Cod sursa(job #184504)

Utilizator hadesgamesTache Alexandru hadesgames Data 23 aprilie 2008 18:57:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#define N 105 
struct ceva
{
	int x,y;
};
ceva coada[10505];
int b[N][N],c[N][N],n,m;
bool a[N][N];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int ver(int x,int y)
{
	if (x<1||x>n)
		return 0;
	if (y<1||y>m)
		return 0;
	return 1;
}
void bfs(int x,int y,int d[N][N])
{
	int i,j,u,p,u2;
	u=1;
	coada[1].x=x;
	coada[1].y=y;
	for (i=1;i<=u;i++)
		for (j=0;j<4;j++)
			  if (ver(coada[i].x+dx[j],coada[i].y+dy[j])&&!d[coada[i].x+dx[j]][coada[i].y+dy[j]]&&!a[coada[i].x+dx[j]][coada[i].y+dy[j]])  
            {  
                 d[coada[i].x+dx[j]][coada[i].y+dy[j]]=d[coada[i].x][coada[i].y]+1;  
                 u++;  
                 coada[u].x=coada[i].x+dx[j];  
                 coada[u].y=coada[i].y+dy[j];  
             }
	
}
int main()
{
	FILE *in,*out;
	int xr,yr,i,j,xj,yj,min,e=0,x,y;
	char s[200];
	in=fopen("rj.in","r");
	out=fopen("rj.out","w");
	fscanf(in,"%d%d\n",&n,&m);
	for (i=1;i<=n;i++)
	{
		fgets(s+1,m+10,in);
		for (j=1;j<=m;j++)
		{
			if (s[j]=='R')
			{
				xr=i;
				yr=j;
				b[xr][yr]=1;				
			}
			if (s[j]=='J')
			{
				xj=i;
				yj=j;
				c[xj][yj]=1;
			}
			if (s[j]=='X')
				a[i][j]=1;
		}
	}	
	bfs(xr,yr,b);
	
	bfs(xj,yj,c);
	e=1;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{	
			if (b[i][j]==c[i][j]&&b[i][j]&&(b[i][j]<min||e))
			{
				min=b[i][j];
				x=i;
				y=j;
			}
				
		}
	fprintf(out,"%d %d %d\n",min-1,x,y);
	fclose(in);
	fclose(out);
	return 0;
}