Cod sursa(job #181531)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 18 aprilie 2008 14:57:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>

#define fin  "rj.in"
#define fout "rj.out"

const int Nmax = 128;

int N,M,xr,yr,xj,yj;

int R[Nmax][Nmax],J[Nmax][Nmax];
char map[Nmax][Nmax];

int deltax[] = { -1, 0, 1, 0, -1, 1,  1, -1 };
int deltay[] = {  0, 1, 0,-1,  1, 1, -1, -1 };

void flood(int a[][Nmax],int x,int y)
{
	int i,j,k,step,flag = 1;
	
	for ( i = 1; i <= N; ++i )
	for ( j = 1; j <= M; ++j )
		a[i][j] = ( map[i][j] == 'X' ) ? ( -1 ) : ( 100000 );
	
	a[x][y] = 1;

	for ( step = 1; flag; ++step )
	{
		flag = 0;

		for ( i = 1; i <= N; ++i )
		for ( j = 1; j <= M; ++j )
			if ( a[i][j] == step )
			for ( k = 0; k < 8; ++k )
				if ( a[i][j] + 1 < a[i + deltax[k]][j + deltay[k]] )
					a[i + deltax[k]][j + deltay[k]] = a[i][j] + 1, flag = 1; 
	}
}

void read_solve()
{
	int i,j,retx,rety,cost;

	freopen(fin,"r",stdin);
	freopen(fout,"w",stdout);

	scanf("%d%d\n",&N,&M);

	for ( i = 1; i <= N; ++i )
		fgets(map[i]+1,Nmax,stdin);

	for ( i = 1; i <= N; ++i )
	for ( j = 1; j <= M; ++j )
	{
		if ( map[i][j] == 'R' )
			xr = i, yr = j;
		if ( map[i][j] == 'J' )
			xj = i, yj = j;
	}

	flood(R,xr,yr); flood(J,xj,yj);

	cost = 100000;

	for ( i = 1; i <= N; ++i )
	for ( j = 1; j <= M; ++j )
		if ( R[i][j] == J[i][j] && R[i][j] > 0 )
		{
			if ( cost > R[i][j] )
				cost = R[i][j], retx = i, rety = j;
		}

	printf("%d %d %d\n",cost,retx,rety);	
}

int main()
{
	read_solve();
	return 0;
}