Cod sursa(job #406094)

Utilizator indestructiblecont de teste indestructible Data 1 martie 2010 10:21:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#define HMAX 121
#define NMAX 102
#define LMAX 10005
int n,m,crd1,crd2,crd3,crd4,best[2][NMAX][NMAX],r;
int l,c,rez=LMAX;
char line[HMAX],mat[NMAX][NMAX];
char marc[2][NMAX][NMAX];
int dlin[]={-1,-1,-1,0,0,1,1,1};
int dcol[]={-1,0,1,-1,1,-1,0,1};
struct coada
{
	char a,b;
};
coada Q[LMAX];
void read()
{
	scanf("%d%d\n",&n,&m);
	int i,j;
	for (i=1; i<=n; i++)
	{
		fgets(line+1,HMAX,stdin);
		for (j=1; j<=m; j++)
		{
			if (line[j]=='X')
				marc[0][i][j]=1,marc[1][i][j]=1,mat[i][j]=1;
			if (line[j]=='R')
				crd1=i,crd2=j;
			if (line[j]=='J')
				crd3=i,crd4=j;
		}
	}
}
inline int ok(int x,int y)
{
	return x>=1 && x<=n && y>=1 && y<=m;
}
void bfs(int x,int y,int tip)
{
	marc[tip][x][y]=1; 
	r=0; 
	Q[++r].a=x; Q[r].b=y;
	int i,j,ant=0,act,x1,y1;
	while (1)
	{
		act=r;
		for (i=ant+1; i<=act; i++)
			for (j=0; j<8; j++)
			{
				x1=Q[i].a+dlin[j]; y1=Q[i].b+dcol[j];
				if (ok(x1,y1) && !marc[tip][x1][y1])
				{
					marc[tip][x1][y1]=1;
					best[tip][x1][y1]=best[tip][Q[i].a][Q[i].b]+1;
					Q[++r].a=x1; Q[r].b=y1;
				}
			}
		ant=act;
		if (act==r)
			return ;
	}
}
void solutie()
{
	int i,j;
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			if (best[0][i][j] && best[0][i][j]==best[1][i][j] && best[0][i][j]<rez)
				rez=best[0][i][j],l=i,c=j;
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	read();
	bfs(crd1,crd2,0);
	bfs(crd3,crd4,1);
	solutie();
	if (crd1==crd3 && crd2==crd4)
		rez=0,l=crd1,c=crd2;
	printf("%d %d %d\n",rez+1,l,c);
	return 0;
}