Cod sursa(job #560235)

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

const int N=101;
int x[N][N];
int Rway[N][N],Jway[N][N];
int n,m;
bool f[N][N];
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()
{
	files();
	char ch;
	scanf("%d%d ",&n,&m);
	for (int i=1;i<=n;++i)
	{
		for (int 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]=-1;
				xR=i;
				yR=j;	
				continue;
			}
			
			x[i][j]=-1;
			xJ=i;
			yJ=j;
		}
		scanf("\n");
	}
	for (int i=1;i<=n;++i)
		x[i][0]=x[i][m+1]=-1;
	for (int i=1;i<=m;++i)
		x[0][i]=x[n+1][i]=-1;
	x[0][0]=-1;
}

void solve()
{
	int p,u,i,j,xnou,ynou;
	p=1;
	q[1].l=xR;
	q[1].c=yR;
	u=1;
	Rway[xR][yR]=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&&!f[xnou][ynou])
			{
				++u;
				q[u].l=xnou;
				q[u].c=ynou;
				Rway[xnou][ynou]=Rway[q[p].l][q[p].c]+1;
				f[xnou][ynou]=true;
			}
		}
		++p;
	}
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			f[i][j]=false;
	
	p=1;
	q[1].l=xJ;
	q[1].c=yJ;
	Jway[xJ][yJ]=1;
	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&&!f[xnou][ynou])
			{
				++u;
				q[u].l=xnou;
				q[u].c=ynou;
				Jway[xnou][ynou]=Jway[q[p].l][q[p].c]+1;
				f[xnou][ynou]=true;
			}
		}
		++p;
	}
	
	int min=999999,mini,minj;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			if (Rway[i][j]==Jway[i][j]&&Rway[i][j])
				if (Rway[i][j]<min)
				{
					min=Rway[i][j];
					mini=i;
					minj=j;
				}
			
	printf("%d %d %d",min,mini,minj);
}

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