Cod sursa(job #416592)

Utilizator Teodor94Teodor Plop Teodor94 Data 12 martie 2010 23:29:07
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<cstdio>

const int N=1<<7;
const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};

char s[N][N];
int nn,x[N*N],y[N*N],x1[N*N],y1[N*N],n,m,romeo[N][N],julieta[N][N];

void lee(int xx,int yy)
{
	for (int i=0;i<8;i++)
	{
		int d1=xx+dx[i],d2=yy+dy[i];
		if (d1>=0 && d1<n && d2>=0 && d2<m && romeo[d1][d2]==-1 && s[d1][d2]!='X')
		{
			nn++;
			x1[nn]=d1;
			y1[nn]=d2;
			romeo[d1][d2]=romeo[xx][yy]+1;
		}
	}
}

void leej(int xx,int yy)
{
	for (int i=0;i<8;i++)
	{
		int d1=xx+dx[i],d2=yy+dy[i];
		if (d1>=0 && d1<n && d2>=0 && d2<m && julieta[d1][d2]==-1 && s[d1][d2]!='X')
		{
			nn++;
			x1[nn]=d1;
			y1[nn]=d2;
			julieta[d1][d2]=julieta[xx][yy]+1;
		}
	}
}

void init()
{
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			romeo[i][j]=-1;
			julieta[i][j]=-1;
		}
}

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	int xr,yr,xj,yj;
	scanf("%d%d\n",&n,&m);
	for (int i=0;i<n;i++)
	{
		gets(s[i]);
		for (int j=0;j<m;j++)
			if (s[i][j]=='R')
			{
				xr=i;
				yr=j;
			}
			else
			if (s[i][j]=='J')
			{
				xj=i;
				yj=j;
			}
	}
	init();
	int nr=1;
	x[1]=xr;
	y[1]=yr;
	romeo[xr][yr]=0;
	while (nr)
	{
		nn=0;
		for (int i=1;i<=nr;i++)
			lee(x[i],y[i]);
		nr=nn;
		for (int i=1;i<=nr;i++)
		{
			x[i]=x1[i];
			y[i]=y1[i];
		}
	}
	nr=1;
	x[1]=xj;
	y[1]=yj;
	julieta[xj][yj]=0;
	while (nr)
	{
		nn=0;
		for (int i=1;i<=nr;i++)
			leej(x[i],y[i]);
		nr=nn;
		for (int i=1;i<=nr;i++)
		{
			x[i]=x1[i];
			y[i]=y1[i];
		}
	}
	int timp=N*N*N,xxx,yyy;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			if (romeo[i][j]==julieta[i][j] && romeo[i][j]<timp && s[i][j]!='X' && romeo[i][j]!=-1)
			{
				timp=romeo[i][j];
				xxx=i;
				yyy=j;
			}
	printf("%d %d %d\n",timp+1,xxx+1,yyy+1);
	return 0;
}