Cod sursa(job #299061)

Utilizator mottyMatei-Dan Epure motty Data 6 aprilie 2009 16:05:15
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.3 kb
#include<cstdio>
#include<deque>
#define INF 10005
#define N 105
using namespace std;
struct cd{
	int x,y;
};
int r[N][N],j[N][N],n,m;
char s[N];
cd R,J;
deque <cd> q;

void cit()
{
	scanf("%d%d\n",&n,&m);
	for( int i=0 ; i<=m+1 ; ++i )
		r[0][i]=r[n+1][i]=j[0][i]=j[n+1][i]=-1;
	for( int i=0 ; i<=n+1 ; ++i )
		r[i][0]=r[i][m+1]=j[i][0]=j[i][m+1]=-1;
	for( int i=1 ; i<=n ; ++i )
	{
		fgets(s+1,N-1,stdin);
		for( int k=1 ; k<=m ; ++k )
			if(s[k]=='X')
				r[i][k]=j[i][k]=-1;
			else if(s[k]=='R')
			{
				R.x=i;
				R.y=k;
			}
			else if(s[k]=='J')
			{
				J.x=i;
				J.y=k;
			}
	}
}

void ver()
{
	char ch='X';
	for( int i=0 ; i<=n+1 ; ++i,printf("\n") )
		for( int k=0 ; k<=m+1 ; ++k )
			if(j[i][k]==INF)
				printf("%3c",ch);
			else
				printf("%3d",j[i][k]);
}

void m_r( cd x )
{
	cd z;
	if( r[x.x-1][x.y-1]==0 )
	{
		z.x=x.x-1;
		z.y=x.y-1;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
	if( r[x.x-1][x.y]==0 )
	{
		z.x=x.x-1;
		z.y=x.y;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
	if( r[x.x-1][x.y+1]==0 )
	{
		z.x=x.x-1;
		z.y=x.y+1;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
	if( r[x.x][x.y-1]==0 )
	{
		z.x=x.x;
		z.y=x.y-1;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
	if( r[x.x][x.y+1]==0 )
	{
		z.x=x.x;
		z.y=x.y+1;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
	if( r[x.x+1][x.y-1]==0 )
	{
		z.x=x.x+1;
		z.y=x.y-1;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
	if( r[x.x+1][x.y]==0 )
	{
		z.x=x.x+1;
		z.y=x.y;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
	if( r[x.x+1][x.y+1]==0 )
	{
		z.x=x.x+1;
		z.y=x.y+1;
		q.push_back(z);
		r[z.x][z.y]=r[x.x][x.y]+1;
	}
}

void m_j( cd x )
{
	cd z;
	if( j[x.x-1][x.y-1]==0 )
	{
		z.x=x.x-1;
		z.y=x.y-1;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
	if( j[x.x-1][x.y]==0 )
	{
		z.x=x.x-1;
		z.y=x.y;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
	if( j[x.x-1][x.y+1]==0 )
	{
		z.x=x.x-1;
		z.y=x.y+1;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
	if( j[x.x][x.y-1]==0 )
	{
		z.x=x.x;
		z.y=x.y-1;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
	if( j[x.x][x.y+1]==0 )
	{
		z.x=x.x;
		z.y=x.y+1;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
	if( j[x.x+1][x.y-1]==0 )
	{
		z.x=x.x+1;
		z.y=x.y-1;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
	if( j[x.x+1][x.y]==0 )
	{
		z.x=x.x+1;
		z.y=x.y;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
	if( j[x.x+1][x.y+1]==0 )
	{
		z.x=x.x+1;
		z.y=x.y+1;
		q.push_back(z);
		j[z.x][z.y]=j[x.x][x.y]+1;
	}
}

void bfs_r()
{
	q.push_back(R);
	while(!q.empty())
	{
		m_r(q.front());
		q.pop_front();
	}
}

void bfs_j()
{
	q.push_back(J);
	while(!q.empty())
	{
		m_j(q.front());
		q.pop_front();
	}
}

void ref()
{
	for( int i=1 ; i<=n ; ++i )
		for( int k=1 ; k<=m ; ++k )
			if( r[i][k]!=j[i][k] || j[i][k]<=0 )
				j[i][k]=INF;
}

void fin()
{
	int min=INF;
	cd rez;
	for( int i=1 ; i<=n ; ++i )
		for( int k=1 ; k<=m ; ++k )
			if( j[i][k]<min )
			{
				min=j[i][k];
				rez.x=i;
				rez.y=k;
			}
	printf("%d %d %d\n",1+min,rez.x,rez.y);
}

int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	cit();
	bfs_r();
	bfs_j();
	ref();
	ver();
	fin();
	return 0;
}