Cod sursa(job #555459)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 15 martie 2011 15:19:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<stdio.h>
#include<string.h>
#define Nmax 109
#define inf 20000

struct point
{
	int x,y;
};

int i,j,nr,m,n,x1,y1,x2,y2,nr2,k,max,imax,jmax,xf,yf,a[Nmax][Nmax],b[Nmax][Nmax],c[Nmax][Nmax],dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
point q[15000],qq[15000];
bool ok;
char x;

int okk()
{
	if (xf<=0) return 0;
	if (yf<=0) return 0;
	if (xf>n) return 0;
	if (yf>m) return 0;
	return 1;
}

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	
	scanf("%d%d\n",&n,&m);
	
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=m;j++)
		{
			scanf("%c",&x);
			if (x=='X') a[i][j]=-1;
			
			if (x=='R') 
			{
				x1=i;
				y1=j;
				a[i][j]=-1;
			}
			if (x=='J')
			{
				x2=i;
				y2=j;
				a[i][j]=-1;
			}
		}
		scanf("%c",&x);
	}
	
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			b[i][j]=inf;
			c[i][j]=inf;
		}
			
	nr=1;
	b[x1][y1]=0;
	q[1].x=x1;
	q[1].y=y1;
	ok=true;
	
	while (ok)
	{
		nr2=0;
		ok=false;
		for (i=1;i<=nr;i++)
			for (k=0;k<=7;k++)
			{
				xf=q[i].x+dx[k];
				yf=q[i].y+dy[k];
				if (okk()&&b[xf][yf]>b[q[i].x][q[i].y]+1&&a[xf][yf]!=-1)
				{
					b[xf][yf]=b[q[i].x][q[i].y]+1;
					nr2++;
					qq[nr2].x=xf;
					qq[nr2].y=yf;
				}
			}
		nr=nr2;
		for (i=1;i<=nr2;i++)
			q[i]=qq[i];
		if (nr2) ok=true;
	}
	
	memset(q,0,sizeof(q));
	nr=1;
	c[x2][y2]=0;
	q[1].x=x2;
	q[1].y=y2;
	ok=true;
	
	while (ok)
	{
		nr2=0;
		ok=false;
		for (i=1;i<=nr;i++)
			for (k=0;k<=7;k++)
			{
				xf=q[i].x+dx[k];
				yf=q[i].y+dy[k];
				if (okk()&&c[xf][yf]>c[q[i].x][q[i].y]+1&&a[xf][yf]!=-1)
				{
					c[xf][yf]=c[q[i].x][q[i].y]+1;
					nr2++;
					qq[nr2].x=xf;
					qq[nr2].y=yf;
				}
			}
		nr=nr2;
		for (i=1;i<=nr2;i++)
			q[i]=qq[i];
		if (nr2) ok=true;
	}
	max=inf;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			if (a[i][j]!=-1&&c[i][j]==b[i][j]&&b[i][j]<max&&c[i][j]!=inf) 
			{
				imax=i;
				jmax=j;
				max=b[i][j];
			}
	printf("%d %d %d\n",max+1,imax,jmax);
	
	return 0;
}