Cod sursa(job #136292)

Utilizator raula_sanChis Raoul raula_san Data 15 februarie 2008 13:37:46
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream.h>
#include <stdio.h>

#define dim 10//1

int N, M, rx, ry, jx, jy;

int R[dim][dim], J[dim][dim], Cx[dim*dim], Cy[dim*dim];

char A[dim];

const int Dx[] = {-1, -1, -1, 1,  1, 1,  0, 0};
const int Dy[] = { 0, -1,  1, 0, -1, 1, -1, 1};

int Ok(int x, int y)
{
	if(x >= 1 && x <= N && y >= 1 && y <= M) return 1;
	return 0;
}

void Bf(int A[dim][dim], int px, int py)
{
	int p, u, x, y, nx, ny, i;

	p = u = 1;

	Cx[p] = px;
	Cy[p] = py;

	A[px][py] = 1;

	while(p <= u)
	{
		x = Cx[p];
		y = Cy[p];

		++ p;

		for(i=0; i<8; ++i)
		{
			nx = x + Dx[i];
			ny = y + Dy[i];

			if(Ok(nx, ny) && !A[nx][ny])
			{
				A[nx][ny] = A[x][y] + 1;

				++ u;
				Cx[u] = nx;
				Cy[u] = ny;
			}
		}
	}
}

int main()
{
	freopen("rj.in", "rt", stdin);
	freopen("rj.out", "wt", stdout);

	int i, j;

	char c;

	for(scanf("%d %d\n", &N, &M), i=0; i<N; ++i)
	{
		fgets(A, dim, stdin);

		for(j=0; j<M; ++j)
		{
			c = A[j];

			if(c == 'R') rx = i + 1, ry = j + 1;
			if(c == 'J') jx = i + 1, jy = j + 1;
			if(c == 'X') R[i+1][j+1] = J[i+1][j+1] = -1;
		}
	}

	R[jx][jy] = -1;
	Bf(R, rx, ry);

	J[rx][ry] = -1;
	Bf(J, jx, jy);

	int min = 0x3f3f3f3f, x, y;

	for(i=1; i<=N; ++i)
		for(j=1; j<=M; ++j)
			if(R[i][j] > 0 && R[i][j] == J[i][j] && R[i][j] < min)
			{
				min = R[i][j];
				x = i;
				y = j;
			}

	printf("%d %d %d", min, x, y);

	fclose(stdin);
	fclose(stdout);
	return 0;
}