Cod sursa(job #243233)

Utilizator AthanaricCirith Gorgor Athanaric Data 12 ianuarie 2009 15:24:12
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#define N 105
const int dlin[4]={-1,0,1,0};
const int dcol[4]={0,1,0,-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[4*N+2][2],x[2],y[2],mod=4*N;
	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)%mod;
		for (i=0; i<4; ++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)%mod;
				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 BloodSeeker(int &x1,int &y1,int &q)
{
	int ok=1;
	for (int i=min(xj,xr); i<=max(xj,xr) && ok; i++)
		for (int j=min(yj,yr); j<=max(yj,yr) && ok; j++)
			if (a[i][j]==a[xj][yj]/2+1)
			{
				printf("%d %d %d\n",i,j,a[xj][yj]/2-1);
				ok=0;
			}
}
void MeetingPoint()
{
	int q=a[xj][yj],x1=xj,y1=yj;
	BloodSeeker(x1,y1,q);
}
void Solve()
{
	Read();
	Bordare();
	Bfs();
	MeetingPoint();
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	Solve();
}