Cod sursa(job #153773)

Utilizator victorsbVictor Rusu victorsb Data 10 martie 2008 18:45:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <stdio.h>

#define Nmax 105
#define INF 0x3f3f3f3fL

const dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int n, m, xr, yr, xj, yj;
int mat[Nmax][Nmax];
long d[2][Nmax][Nmax];
char sir[Nmax];
int Qx[Nmax * Nmax];
int Qy[Nmax * Nmax];

void citire()
{
	int i, j;

	scanf("%d %d\n", &n, &m);
	for (i = 1; i <= n; ++i)
	{
		fgets(sir + 1, Nmax, stdin);
		for (j = 1; j <= m; ++j)
		{
			if (sir[j] != 'X')
				mat[i][j] = 1;
			if (sir[j] == 'R')
				xr = i, yr = j;
			if (sir[j] == 'J')
				xj = i, yj = j;
		}
	}
}

void BF(int x0, int y0, int t)
{
	int i, j, st = 0, dr = 1, x, y, dir;

	for (i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			d[t][i][j] = INF;

	Qx[dr] = x0;
	Qy[dr] = y0;
	d[t][x0][y0] = 1;

	while (st < dr)
	{
		x = Qx[++st];
		y = Qy[st];
		for (dir = 0; dir < 8; ++dir)
		{
			x0 = x + dx[dir];
			y0 = y + dy[dir];
			if (mat[x0][y0] && d[t][x0][y0] > d[t][x][y] + 1)
			{
				d[t][x0][y0] = d[t][x][y] + 1;
				Qx[++dr] = x0;
				Qy[dr] = y0;
			}
		}
	}
}

void solve()
{
	int i, j, sx, sy;
	long best = INF;

	BF(xr, yr, 0);
	BF(xj, yj, 1);

	for (i = 1; i <= n; ++i)
		for (j = 1; j <= m; ++j)
			if (d[0][i][j] == d[1][i][j] && d[0][i][j] < best)
			{
				sx = i;
				sy = j;
				best = d[0][i][j];
			}

	printf("%ld %d %d\n", best, sx, sy);
}

int main()
{
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);

	citire();
	solve();

	return 0;
}