Cod sursa(job #78166)

Utilizator marius135Dumitran Adrian Marius marius135 Data 15 august 2007 19:05:08
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<stdio.h>
#define maxn 128

long x[8] ={0,0,1,1,1,-1,-1,-1},y[8]={1,-1,0,1,-1,0,1,-1};
long n,m,v[maxn][maxn],sol[maxn*maxn][3],sel[maxn][maxn];

void bf(long a,long b,long xx,long yx)
{
	sol[1][0] = a;
	sol[1][1] = b;
	sol[1][2] = 0;
	long poz = 1;
	long last = 1,h;
	sel[a][b] = 1;
	for( ; poz <= last; poz++)
	{
		a = sol[poz][0];
		b = sol[poz][1];
		if(a==xx && b == yx) return ;
		h = sol[poz][2];
		
		for(long i =0; i < 8; i++)
		{
			long c = a + x[i];
			long d = b + y[i];
			if(d>0 && c>0 && c <= n && d <= m && sel[c][d] == 0 && v[c][d] == 0)
				{
				sel[c][d] = h+1;
				sol[++last][0] = c;
				sol[last][1] = d;
				sol[last][2] = h+1;
				}
		}
	}
}
int main()
{
	long i,j,x1,x2,y1,y2;
	char c;
	
	
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	
	scanf("%ld %ld",&n,&m);
	scanf("%c",&c);
	while(c!='\n')
		scanf("%c",&c);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%c",&c);
			while(!(c=='R' || c=='J' || c==' ' || c=='X' || c=='\n'))
				scanf("%c",&c);
			if(c=='\n')
				break;
			v[i][j] = 0;
			if(c=='J')
			{
				x1 = i;
				y1 = j;
			}
			if(c=='R')
			{
				x2 = i;
				y2 = j;
			}
			if(c=='X')
				v[i][j] = 1;
		}
		if(j==m+1 && i!=n)
		{
			scanf("%c",&c);
			while(c!='\n')
				scanf("%c",&c);
		}
	
	}
	v[0][0] = 0;
	bf(x1,y1,x2,y2);
	long t = sel[x2][y2];
	t/=2;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(sel[i][j]==t)
			{
				printf("%ld %ld %ld\n",t+1,i,j);
				return 0;
			}
	
	
	return 0;
}