Cod sursa(job #79769)

Utilizator MariusMarius Stroe Marius Data 23 august 2007 20:01:29
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <iomanip>
using namespace std;

long rj[101][101], r1[101][101],j1[101][101];
long i,j,n,m,cri,crj,cji,cjj;
char c;

void drum_romeo(int l, int c, int k)
{	
	if( c>1 && r1[l][c-1] >= 0 )
		if( r1[l][c-1] > k+1 )
		{	r1[l][c-1] = k+1;
			drum_romeo(l,c-1,k+1);
		}
	if( c<m && r1[l][c+1] >= 0 )
		if( r1[l][c+1] > k+1 )
		{	r1[l][c+1] = k+1;
			drum_romeo(l,c+1,k+1);
		}
	if( l>1 && r1[l-1][c] >= 0 )
		if( r1[l-1][c] > k+1 )
		{	r1[l-1][c] = k+1;
			drum_romeo(l-1,c,k+1);
		}
	if( l<n && r1[l+1][c] >= 0 )
		if( r1[l+1][c] > k+1 )
		{	r1[l+1][c] = k+1;
			drum_romeo(l+1,c,k+1);
		}
}
void drum_julieta(int l, int c, int k)
{	
	if( c>1 && j1[l][c-1] >= 0 )
		if( j1[l][c-1] > k+1 )
		{	j1[l][c-1] = k+1;
			drum_julieta(l,c-1,k+1);
		}
	if( c<m && j1[l][c+1] >= 0 )
		if( j1[l][c+1] > k+1 )
		{	j1[l][c+1] = k+1;
			drum_julieta(l,c+1,k+1);
		}
	if( l>1 && j1[l-1][c] >= 0 )
		if( j1[l-1][c] > k+1 )
		{	j1[l-1][c] = k+1;
			drum_julieta(l-1,c,k+1);
		}
	if( l<n && j1[l+1][c] >= 0 )
		if( j1[l+1][c] > k+1 )
		{	j1[l+1][c] = k+1;
			drum_julieta(l+1,c,k+1);
		}
}
void search()
{
	long min = 200000, l, c;
	for( i=1; i<=n; i++ )
		for( j=1; j<=m; j++ )
			if( r1[i][j] == j1[i][j] && r1[i][j] > 0 && j1[i][j] > 0 )
				if( min > r1[i][j] )
				{	
					min = r1[i][j];
					l = i, c = j;
				}
	FILE *fo = fopen("rj.out", "w");

	fprintf(fo, "%d %d %d\n", l, c, min);
	fclose(fo);
}

int main(void)
{
	FILE *fi = fopen("rj.in", "r");

	fscanf(fi, "%d %d\n", &n, &m);
	for( i=1; i<=n; i++ )
	{	
		for( j=1; j<=m; j++ )
		{	
			fscanf(fi, "%c", &c);
			if( c == 'X' )
				rj[i][j]= r1[i][j]= j1[i][j]= -1;
			else if( c == 'R' )
			{	rj[i][j] = -2; r1[i][j] = -2, j1[i][j] = -2; cri=i, crj=j; }
			else if( c == 'J' )
			{	rj[i][j] = -3; r1[i][j] = j1[i][j] = -3; cji=i, cjj=j; }
			else 
				rj[i][j] = r1[i][j] = j1[i][j] = 100010;
		}
		fscanf(fi, "%c\n", &c);
	}
	fclose(fi);
	drum_romeo(cri,crj,0);
	drum_julieta(cji,cjj,0);
	search();

	return 0;
}