Cod sursa(job #121613)

Utilizator za_wolfpalianos cristian za_wolf Data 9 ianuarie 2008 00:27:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<stdio.h>
#include<string.h>
int l[]={1,1,1,-1,-1,-1,0,0};
int c[]={0,1,-1,0,1,-1,1,-1};
char x[151][151],cc,jeg[151][151];
int in,sf,rez,i,j,n,m,k,xi,yi,xf,yf,y[115][115],z[115][115];
struct kkt
{
	int a,b,k;
};
kkt q[11111];
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d%c%c",&n,&m,&cc,&cc);
	m--;
	for (i=1;i<=n;i++)
	{
		fgets(x[i],114,stdin);
		for (j=0;j<strlen(x[i]);j++)
		if (x[i][j]=='X') jeg[i][j]=1;
//		scanf("%c",&cc);
	}
	for (i=1;i<=n;i++)
		for (j=0;j<=m;j++)
		{
			if (x[i][j]=='R') {xi=i; yi=j;x[i][j]=' ';}
			if (x[i][j]=='J') {xf=i; yf=j;x[i][j]=' ';}
		}

	q[1].a=xi;
	q[1].b=yi;
	q[1].k=1;
	y[xi][yi]=1;
	in=1;
	sf=1;
	while (in<=sf)
	{
		for (i=0;i<=7;i++)
		   if (jeg[q[in].a+l[i]][q[in].b+c[i]]==0&&q[in].a+l[i]>0&&q[in].a+l[i]<=n&&q[in].b+c[i]>=0&&q[in].b+c[i]<=m&&y[q[in].a+l[i]][q[in].b+c[i]]==0)
		   {
				sf++;
				q[sf].a=q[in].a+l[i];
				q[sf].b=q[in].b+c[i];
				q[sf].k=q[in].k+1;
				y[q[sf].a][q[sf].b]=q[sf].k;

		   }
		in++;
	}


	q[1].a=xf;
	q[1].b=yf;
	q[1].k=1;
	z[xf][yf]=1;
	in=1;
	sf=1;
	while (in<=sf)
	{
		for (i=0;i<=7;i++)
		   if (jeg[q[in].a+l[i]][q[in].b+c[i]]==0&&q[in].a+l[i]>0&&q[in].a+l[i]<=n&&q[in].b+c[i]>=0&&q[in].b+c[i]<=m&&z[q[in].a+l[i]][q[in].b+c[i]]==0)
		   {
				sf++;
				q[sf].a=q[in].a+l[i];
				q[sf].b=q[in].b+c[i];
				q[sf].k=q[in].k+1;
				z[q[sf].a][q[sf].b]=q[sf].k;
		   }
		in++;
	}

	rez=10001;
	for (i=1;i<=n;i++)
		for (j=0;j<=m;j++)
		if (y[i][j]==z[i][j]&&y[i][j]<rez&&y[i][j]!=0) {rez=y[i][j]; xi=i; yi=j;}
	printf("%d %d %d\n",rez,xi,yi+1);

	return 0;
}