Cod sursa(job #184529)

Utilizator hadesgamesTache Alexandru hadesgames Data 23 aprilie 2008 19:36:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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,1,1,-1,-1};
const int dy[]={1,-1,0,0,-1,1,-1,1};
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;
	u=1;
	coada[1].x=x;
	coada[1].y=y;
	for (i=1;i<=u;i++)
		for (j=0;j<8;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=0,yr=0,i,j,xj=0,yj=0,min=0,e=0,x=0,y=0;
	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);
	/*for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
			fprintf(stdout,"%d ",b[i][j]);
		fprintf(stdout,"\n");
	}*/
	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;
				e=0;
			}
			//if (i==12;j==2)
				//fprintf(stdout,"%d %d %d \n",b[i][j]==c[i][j],b[i][j],b[i][j]				
		}
	fprintf(out,"%d %d %d\n",min,x,y);
	fclose(in);
	fclose(out);
	return 0;
}