Cod sursa(job #185200)

Utilizator AndreyPAndrei Poenaru AndreyP Data 24 aprilie 2008 21:40:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include<stdio.h>
int n,m,a[110][110],b[110][110],xf,yf,rez=1000000;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-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++)
	{
		for(j=1; j<=m; j++)
		{
			scanf("%c",&aux);
			switch(aux)
			{
				case ' ': break;
				case 'X': a[i][j]=-1; break;
				case 'R': {r.x=i; r.y=j; a[i][j]=-1;} break;
				case 'J': {ju.x=i; ju.y=j; a[i][j]=-1;} break;
			}
		}
		scanf("\n");
	}
	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;
	co[0]=r;
	while(inc<=sf)
	{
		now=co[inc++];
		for(i=0; i<4; 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;
			}
		}
	}
	a[r.x][r.y]=0;
}
void bfju()
{
	int inc=0,sf=0,i;
	rom now,next;
	b[r.x][r.y]=0;
	co[0]=ju;
	while(inc<=sf)
	{
		now=co[inc++];
		for(i=0; i<4; 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;
			}
		}
	}
	b[ju.x][ju.y]=0;
}
inline int max(int k1,int k2)
{
	if(k1<k2)
		return k2;
	return k1;
}
void afla()
{
	int i,j,aux;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=m; j++)
		{
			if((a[i][j]!=-1)&&(a[i][j]!=0))
			{
				aux=max(a[i][j],b[i][j]);
				if(aux<rez)
				{
					rez=aux;
					xf=i;
					yf=j;
				}
			}
		}
	}
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	citeste();
	bfr();
	bfju();
	int i,j;
	/*for(i=0; i<=n+1; i++)
	{
		for(j=0; j<=m+1; j++)
			printf("%2d ",a[i][j]);
		printf("\n");
	}
	printf("\n");
	for(i=0; i<=n+1; i++)
	{
		for(j=0; j<=m+1; j++)
			printf("%2d ",b[i][j]);
		printf("\n");
	}*/
	afla();
	printf("%d %d %d\n",rez,xf,yf);
	return 0;
}