Cod sursa(job #185230)

Utilizator AndreyPAndrei Poenaru AndreyP Data 24 aprilie 2008 22:16:00
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<stdio.h>
int n,m,a[110][110],b[110][110],xf,yf,rez=1000000;
char c[115];
const int dx[]={1,0,-1,0,-1,-1,1,1};
const int dy[]={0,1,0,-1,-1,1,1,-1};
struct rom
{
	int x,y;
};
rom r,ju,co[10010];
void citeste()
{
	int i,j;
	char aux;
	scanf("%d%d\n",&n,&m);
	for(i=0; i<=n+1; i++)
		a[i][0]=a[i][m+1]=-1;
	for(i=0; i<=m; i++)
		a[0][i]=a[n+1][i]=-1;
	for(i=1; i<=n; i++)
	{
		fgets(c+1,114,stdin);
		for(j=1; j<=m; j++)
		{
			aux=c[j];
			switch(aux)
			{
				case ' ': break;
				case 'X': a[i][j]=-1; break;
				case 'R': {r.x=i; r.y=j;} break;
				case 'J': {ju.x=i; ju.y=j;} break;
			}
		}
	}
	n++;
	m++;
	for(i=0; i<=n; i++)
	{
		for(j=0; j<=m; j++)
			b[i][j]=a[i][j];
	}
	n--;
	m--;
}
void bfr()
{
	int inc=0,sf=0,i;
	rom now,next;
	//a[ju.x][ju.y]=0;
	a[r.x][r.y]=1;
	co[0]=r;
	while(inc<=sf)
	{
		now=co[inc++];
		for(i=0; i<8; i++)
		{
			next.x=now.x+dx[i];
			next.y=now.y+dy[i];
			if(a[next.x][next.y]==0)
			{
				co[++sf]=next;
				if(a[now.x][now.y]==-1)
					a[next.x][next.y]=1;
				else
					a[next.x][next.y]=a[now.x][now.y]+1;
			}
		}
	}
}
void bfju()
{
	int inc=0,sf=0,i;
	rom now,next;
	//b[r.x][r.y]=0;
	b[ju.x][ju.y]=1;
	co[0]=ju;
	while(inc<=sf)
	{
		now=co[inc++];
		for(i=0; i<8; i++)
		{
			next.x=now.x+dx[i];
			next.y=now.y+dy[i];
			if(b[next.x][next.y]==0)
			{
				co[++sf]=next;
				if(b[now.x][now.y]==-1)
					b[next.x][next.y]=1;
				else
					b[next.x][next.y]=b[now.x][now.y]+1;
			}
		}
	}
}
void afla()
{
	int i,j;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
		{
			if((a[i][j]!=-1)&&(a[i][j]!=0))
			{
				if(a[i][j]==b[i][j])
				{
					if(a[i][j]<rez)
					{
						rez=a[i][j];
						xf=i;
						yf=j;
					}
				}
			}
		}
	}
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	citeste();
	bfr();
	bfju();
	afla();
	printf("%d %d %d\n",rez,xf,yf);
	return 0;
}