Cod sursa(job #244299)

Utilizator AthanaricCirith Gorgor Athanaric Data 14 ianuarie 2009 21:15:19
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>
#define N 105
const int dlin[8]={-1,0,1,0,-1,-1,1,1};
const int dcol[8]={0,1,0,-1,-1,1,-1,1};
int a[N][N],xj,yj,xr,yr,n,m;
void Read()
{
	char c;
	scanf("%d%d\n",&n,&m);
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			scanf("%c",&c);
			if (c==' ')
				a[i][j]=0;
			if (c=='X')
				a[i][j]=-1;
			if (c=='J')
			{
				xj=i;
				yj=j;
			}
			if (c=='R')
			{
				a[i][j]=1;
				xr=i;
				yr=j;
			}
		}
		scanf("\n");
	}
}

void Bordare()
{
	for (int i=0; i<=n+1; i++)
	{
		a[i][0]=-1;
		a[i][m+1]=-1;
	}
	for (int j=0; j<=m+1; j++)
	{
		a[0][j]=-1;
		a[n+1][j]=-1;
	}
}
void Bfs()
{
	int i,p,u,coada[N*N][2],x[2],y[2];
	p=u=0;
	coada[u][0]=xr;
	coada[u++][1]=yr;
	a[xr][yr]=1;
	while (p!=u)
	{
		x[0]=coada[p][0];
		x[1]=coada[p][1];
		p=p+1;
		for (i=0; i<8; ++i)
		{
			y[0]=x[0]+dlin[i];
			y[1]=x[1]+dcol[i];
			if (a[y[0]][y[1]]==0)
			{
				coada[u][0]=y[0];
				coada[u][1]=y[1];
				u=u+1;
				a[y[0]][y[1]]=1+a[x[0]][x[1]];
			}
		}
	}
}
int min(int a,int b)
{
	if (a>b)
		return b;
	return a;
}
int max(int a,int b)
{
	if (a>b)
		return a;
	return b;
}
void MeetingPoint()
{
	int q=(a[xj][yj]-1)/2+1,q1=a[xj][yj],x1=xj,y1=yj;
	while (q1!=q)
	{
		for (int i=0; i<=7; i++)
			if (a[x1+dlin[i]][y1+dcol[i]]==q1-1)
			{
				x1=x1+dlin[i];
				y1=y1+dcol[i];
				q1--;
			}
	}
	printf("%d %d %d\n",x1,y1,q-1);
}
void Solve()
{
	Read();
	Bordare();
	Bfs();
	MeetingPoint();
	
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	Solve();
}