Cod sursa(job #560256)

Utilizator nightwish0031Vlad Radu Cristian nightwish0031 Data 18 martie 2011 13:27:47
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<cstdio>

const int N=101;
int x[N][N],y[N][N];
int n,m;
int dx[]={-1,-1,0,1,1,1,0,-1},dy[]={0,1,1,1,0,-1,-1,-1};
int xJ,yJ,xR,yR;
struct queue
{
	int l,c;
};

queue q[N*N];
void files()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
}

void read()
{
	int j,i;
	files();
	char ch;
	scanf("%d%d ",&n,&m);
	for (i=1;i<=n;++i)
	{
		for (j=1;j<=m;++j)
		{
			scanf("%c",&ch);
			if (ch=='X')
			{
				x[i][j]=-1;
				continue;
			}
			if (ch==' ')
			{
				x[i][j]=0;
				continue;
			}
			if (ch=='R') 
			{
				x[i][j]=0;
				xR=i;
				yR=j;	
				continue;
			}
			
			x[i][j]=0;
			xJ=i;
			yJ=j;
		}
		scanf("\n");
	}
	for (i=1;i<=n;++i)
		x[i][0]=x[i][m+1]=-1;
	for (i=1;i<=m;++i)
		x[0][i]=x[n+1][i]=-1;
	x[0][0]=-1;
	for (i=0;i<=n+1;++i)
		for (j=0;j<=m+1;++j)
			y[i][j]=x[i][j];
}

void solve()
{
	int p,u,i,j,xnou,ynou;
	p=1;
	q[1].l=xR;
	q[1].c=yR;
	u=1;
	while (p<=u)
	{
		for (i=0;i<8;++i)
		{
			xnou=q[p].l+dx[i];
			ynou=q[p].c+dy[i];
			if (x[xnou][ynou]==0)
			{
				++u;
				q[u].l=xnou;
				q[u].c=ynou;
				x[xnou][ynou]=x[q[p].l][q[p].c]+1;				
			}
		}
		++p;
	}
	
	
	p=1;
	q[1].l=xJ;
	q[1].c=yJ;
	u=1;
	while (p<=u)
	{
		for (i=0;i<8;++i)
		{
			xnou=q[p].l+dx[i];
			ynou=q[p].c+dy[i];
			if (y[xnou][ynou]==0)
			{
				++u;
				q[u].l=xnou;
				q[u].c=ynou;
				y[xnou][ynou]=y[q[p].l][q[p].c]+1;
			}
		}
		++p;
	}
	
	int min=999999,mini,minj;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (x[i][j]==y[i][j]&&x[i][j]>0)
				if (x[i][j]<min)
				{
					min=x[i][j];
					mini=i;
					minj=j;
				}
			
	printf("%d %d %d",min+1,mini,minj);
}

int main()
{
	read();
	solve();
	
	
	return 0;
}