Cod sursa(job #136368)

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

#define dim 105

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

int R[dim][dim], J[dim][dim], Cx2[2*dim], Cy2[2*dim], Cx1[2*dim], Cy1[2*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;

	Cx1[p] = px;
	Cy1[p] = py;

	A[px][py] = 1;

	for(;;)
	{
		for(u=0; p; --p)
		{
			x = Cx1[p];
			y = Cy1[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;
					Cx2[u] = nx;
					Cy2[u] = ny;
				}
			}
		}

		if(!u) break;

		p = u;
		for(; u; --u)
		{
			Cx1[u] = Cx2[u];
			Cy1[u] = Cy2[u];
		}
	}
}

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("%2d ", J[i][j]);
        }
//        printf("\n");    
    }

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

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