Cod sursa(job #117263)

Utilizator mithyPopovici Adrian mithy Data 21 decembrie 2007 00:23:16
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#define ZID 9
#define NMax 101
#define ND 8
#define INF 100000

int n, m, xj, yj, xr, yr;
int a[NMax][NMax], b[NMax][NMax];
std::ifstream f("rj.in");
std::ofstream g("rj.out"); 

struct poz
{
	int x, y;
}C[NMax], aux;
int in, sf;
int dx[] = {-1, 0, 1, 0,-1, 1, 1,-1};
int dy[] = { 0, 1, 0,-1, 1, 1,-1,-1};

void citire();
void rez();
void lee( int a[NMax][NMax], int xs, int ys, int xf, int yf );
int main()
{
	citire();
	rez();
	return 0;
}
void lee( int z[NMax][NMax], int xs, int ys, int xf, int yf )
{
	int i, j;
	in = sf = 0;
	C[0].x = xs;
	C[0].y = ys;
	z[xs][ys] = 1;

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

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

		for (i=0; i<ND; i++)
			if ( z[aux.x+dx[i]][aux.y+dy[i]] == 0 )
			{
				sf++;
				C[sf].x = aux.x+dx[i];
				C[sf].y = aux.y+dy[i];
				z[aux.x+dx[i]][aux.y+dy[i]] = 1 + z[aux.x][aux.y];
			}
	}

// 	for (i=1; i<=n; i++)
// 	{
// 		for (j=1; j<=m; j++)
// 		{
// 			g << z[i][j] << ' ';
// 		}
// 		g << '\n';
// 	}
// 	g << '\n';

}
void rez()
{
	int i, j, x, y, min = INF;
	lee(a, xj, yj, xr, yr );
	lee(b, xr, yr, xj, yj );

	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 )
				if ( a[i][j] < min )
				{
					min = a[i][j];
					x = i;
					y = j;
				}
	g << x << ' ' << y << ' ' << min-1 << '\n';
}
void citire()
{
	int i, j;
	char aux[NMax];
	f >> n >> m; f.get();

	for (i=0; i<n; i++)
	{
		f.getline( aux, NMax, '\n' );
		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] = ZID;
				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;
}