Cod sursa(job #117277)

Utilizator mithyPopovici Adrian mithy Data 21 decembrie 2007 01:18:46
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#define ZID -1
#define NMax 105
#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[100000], 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 tip );
int main()
{
	citire();
	rez();
	return 0;
}
void lee( int tip )
{
	int i, j, xs, ys, xf, yf;

	if (tip == 1)
	{
		xs = xj; xf = xr;
		ys = yj; yf = yr;
	}
	else
	{
		xs = xr; xf = xj;
		ys = yr; yf = yj;
	}
	in = sf = 0;
	C[0].x = xs;
	C[0].y = ys;

	if ( tip == 1 )
	{
		a[xs][ys] = 1;

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

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

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

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

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

			for (i=0; i<ND; i++)
				if ( b[aux.x+dx[i]][aux.y+dy[i]] == 0 )
				{
					sf++;
					C[sf].x = aux.x+dx[i];
					C[sf].y = aux.y+dy[i];
					b[aux.x+dx[i]][aux.y+dy[i]] = 1 + b[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(1);
	lee(2);

	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 << min << ' ' << x << ' ' << y << '\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;
}