Cod sursa(job #298903)

Utilizator mottyMatei-Dan Epure motty Data 6 aprilie 2009 14:16:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<cstdio>
#include<deque>
#define N 101
#define INF 100001
#define max(a,b) a>b ? a:b
#define IN freopen("rj.in","r",stdin)
#define OUT freopen("rj.out","w",stdout)
using namespace std;

int r[N][N],n,m,j[N][N];

char rd[N];

struct cd{
	int x,y;
};

deque <cd> q;

cd ro,ju;

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

void ver()
{
	char romeo='R',julieta='J';
	for( int i=0 ; i<=n+1 ; ++i,printf("\n") )
		for( int k=0 ; k<=m+1 ; ++k )
			if( ro.x==i && ro.y==k )
				printf("%3c",romeo);
			else if( ju.x==i && ju.y==k)
				printf("%3c",julieta);
			else
				printf("%3d",j[i][k]);
}

void m1( cd x )
{
	cd z;
	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]==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][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;
	}
}

void m2( cd x )
{
	cd z;
	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]==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][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;
	}
}

void bfs_r()
{
	q.push_back(ro);
	while(!q.empty())
	{
		m1(q.front());
		q.pop_front();
	}
}

void bfs_j()
{
	q.push_back(ju);
	while(!q.empty())
	{
		m2(q.front());
		q.pop_front();
	}
}

void ref()
{
	for( int i=1 ; i<=n ; ++i )
		for( int k=1 ; k<=m ; ++k )
			if( j[i][k]!=r[i][k] )
				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]>0 && j[i][k]<min )
			{
				rez.x=i;
				rez.y=k;
				min=j[i][k];
			}
	printf("%d %d %d\n",min,rez.x,rez.y);
}

int main()
{
	IN;OUT;
	cit();
	bfs_r();
	bfs_j();
	ref();
	//ver();
	fin();
	return 0;
}