Cod sursa(job #244320)

Utilizator AthanaricCirith Gorgor Athanaric Data 14 ianuarie 2009 21:40:04
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 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],b[N][N],xj,yj,xr,yr,n,m,minx=100000,ip,jp;
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]=b[i][j]=0;
			if (c=='X')
				a[i][j]=b[i][j]=-1;
			if (c=='J')
			{
				xj=i;
				yj=j;
			}
			if (c=='R')
			{
				xr=i;
				yr=j;
			}
		}
		scanf("\n");
	}
}

void Bordare()
{
	for (int i=0; i<=n+1; i++)
	{
		a[i][0]=b[i][0]=-1;
		a[i][m+1]=b[i][m+1]=-1;
	}
	for (int j=0; j<=m+1; j++)
	{
		a[0][j]=b[0][j]=-1;
		a[n+1][j]=b[n+1][j]=-1;
	}
}
void BfsR()
{
	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]];
			}
		}
	}
}
void BfsJ()
{
	int i,p,u,coada[N*N][2],x[2],y[2];
	p=u=0;
	coada[u][0]=xj;
	coada[u++][1]=yj;
	b[xj][yj]=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 (b[y[0]][y[1]]==0)
			{
				coada[u][0]=y[0];
				coada[u][1]=y[1];
				u=u+1;
				b[y[0]][y[1]]=1+b[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()
{
	minx=100000; int colmin=m,linmin=n;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			if (a[i][j]>0&&a[i][j]==b[i][j]&&a[i][j]<minx&&j<colmin&&i<linmin)
			{
				minx=a[i][j];
				ip=i;
				jp=j;
			}
}
void Print(int x[N][N])
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
			printf("%d ",x[i][j]);
		printf("\n");
	}
	printf("\n\n");
}
void Solve()
{
	Read();
	Bordare();
	BfsR();
	BfsJ();
	MeetingPoint();
	printf("%d %d %d\n",minx,ip,jp);
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	Solve();
}