Cod sursa(job #117452)

Utilizator mithyPopovici Adrian mithy Data 21 decembrie 2007 15:04:59
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <stdio.h>
#define NMax 105
#define ZID -1
#define ND 8
#define INF 32000

int n, m;
int xr, yr, xj, yj;
int a[NMax][NMax], b[NMax][NMax];
FILE *f, *g;

int in, sf;
struct coada
{ int x, y; } C[NMax*NMax], aux;
//           N NE  E ES  S SV  V NV
int dx[] = {-1,-1, 0, 1, 1, 1, 0,-1} ;
int dy[] = { 0, 1, 1, 1, 0,-1,-1,-1} ;

void citire();
void lee( int x[NMax][NMax], int xs, int ys, int xf, int yf );
void rez();

int main()
{
	citire();
	rez();
	return 0;
}
void rez()
{
	int i, j, x, y, tmin = INF;

	lee( a, xr, yr, xj, yj );
	lee( b, xj, yj, xr, yr );

	for (i=1; i<=n; i++)
		 for (j=1; j<=m; j++)
			if ( a[i][j] == b[i][j] && a[i][j] != ZID && a[i][j] != 0 && tmin >a[i][j] )
			{
				tmin = a[i][j];
				x = i;
				y = j;
			}

	fprintf( g, "%d %d %d\n", tmin, x, y );
}
void lee( int x[NMax][NMax], int xs, int ys, int xf, int yf )
{
	int i, j;
	C[0].x = xs;
	C[0].y = ys;
	in = sf = 0;
	x[xs][ys] = 1;

	while ( in <= sf )
	{
		aux = C[in++];

		if ( aux.x == xf && aux.y == yf )
			break;

		for (i=0; i<ND; i++)
			if ( x[aux.x+dx[i]][aux.y+dy[i]] == 0 )
			{
				x[aux.x+dx[i]][aux.y+dy[i]] = x[aux.x][aux.y] + 1;
				sf++;
				C[sf].x = aux.x+dx[i];
				C[sf].y = aux.y+dy[i];
			}
	}
}
void citire()
{
	int i, j;
	char aux[NMax];
	f = fopen("rj.in", "rt");
	g = fopen("rj.out","wt");

	fscanf( f, "%d %d", &n, &m );
	fgets( aux, NMax, f );

	for (i=0; i<n; i++)
	{
		fgets( aux, NMax, f );
		for (j=0; j<m; j++)
		{
			if ( aux[j] == 'R' )
			{
				xr = i+1; yr = j+1;
			}
			if ( aux[j] == 'J' )
			{
				xj = i+1; yj = j+1;
			}
			if ( aux[j] == 'X' )
			{
				a[i+1][j+1] = b[i+1][j+1] = ZID;
			}
		}
	}

	for (i=0; i<=n+1; i++)
		a[i][0] = a[i][m+1] = b[i][0] = b[i][m+1] = ZID;
	for (i=0; i<=m+1; i++)
		a[0][i] = a[n+1][i] = b[0][i] = b[n+1][i] = ZID;
}