Cod sursa(job #79527)

Utilizator vladcoderVlad Ion vladcoder Data 22 august 2007 23:04:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>
#include <string.h>
#define FIN "rj.in"
#define FOUT "rj.out"
#define NMAX 110

int A[NMAX][NMAX], R[NMAX][NMAX], J[NMAX][NMAX];
char S[NMAX];
FILE * fin, * fout;
int N, M, i, j, rx, ry, jx, jy, x, y, min;
int oriz[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int vert[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };

typedef struct nod
{
	int x, y;
} NOD;

NOD Q[NMAX*NMAX];

int inside( int x, int y )
{
	if (( x < 1 ) || ( x > N ) || ( y < 1 ) || ( y > M ) ) return 0;
	else return 1;
}


void BFS( int x, int y, int D[NMAX][NMAX] )
{
	int p, u, l, c, ll, cc;
	memset( D, 0, sizeof( D ) );
	D[x][y] = 1; p = 1; u = 1;
	Q[1].x = x; Q[1].y = y;
	while ( p <= u )
	{
		l = Q[p].x; c = Q[p].y;
		for( i = 0; i < 8; i++ )
		{
			ll = l + oriz[i];
			cc = c + vert[i];
			if ( inside( ll, cc ) ) 
				if ( (!D[ll][cc]) && (!A[ll][cc]) )
				{
					D[ll][cc] = D[l][c] + 1;
					u++; Q[u].x = ll; Q[u].y = cc;
				}
		}
		p++;
	}
	
}

int main()
{
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d %d\n", &N, &M );
	memset( A, 0, sizeof(A) );
	for( i = 1; i <= N; i++)
	{
	  fgets( S, NMAX, fin );
	  for( j = 0; j < M; j++ )
					
			switch (S[j])
		{
			case 'R' : rx = i; ry = j+1;
		             break;
			case 'J' : jx = i; jy = j+1;
				     break;
			case 'X' : A[i][j+1] = 1;
				     break;  
		}
		

	}

	BFS( rx, ry, R );
	BFS( jx, jy, J );
	min = 10000000;
	for( i = 1; i <= N; i++ )
		for( j = 1; j <= M; j++ )
			if ( (R[i][j]) && ( J[i][j] ) )
			if ( R[i][j] == J[i][j] )
				if (R[i][j] < min )
				{
					min = R[i][j];
					x = i; y = j;
				}
	
	fprintf( fout, "%d %d %d\n", min, x, y );
	fclose( fin );
	fclose( fout );
	return 0;
}