Cod sursa(job #90084)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 8 octombrie 2007 16:55:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#include <vector>

using namespace std;

const int N_MAX = 101;
const int INF = 2000000000;

int R[N_MAX][N_MAX], J[N_MAX][N_MAX];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int N, M;

pair <int, int> Q[N_MAX * N_MAX];

void BF(int x, int y, int A[N_MAX][N_MAX])
{
	int in = 1, sf = 2, i, xx, yy;
	pair <int, int> nod;

	Q[1] = make_pair(x, y);
	while (in != sf) {
		nod = Q[in];
		in ++;

		for (i = 0; i < 8; i ++) {
			xx = nod.first + dx[i];
			yy = nod.second + dy[i];

			if (1 <= xx && xx <= N && 1 <= yy && yy <= M && A[xx][yy] != -1 && A[nod.first][nod.second] + 1 < A[xx][yy]) {
				A[xx][yy] = A[nod.first][nod.second] + 1;
				Q[sf] = make_pair(xx, yy);
				sf ++;
			}
		}
	}
}

int i, j, x1, y1, x2, y2;

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

	char c;

	scanf("%d %d\n", &N, &M);
	for (i = 1; i <= N; i ++) {
		for (j = 1; j <= M; j ++) {
			if (j < M) scanf("%c", &c);
			else scanf("%c ", &c);

			if (c == ' ') R[i][j] = INF, J[i][j] = INF;
			if (c == 'R') R[i][j] = 0, x1 = i, y1 = j, J[i][j] = INF;
			if (c == 'J') J[i][j] = 0, x2 = i, y2 = j, R[i][j] = INF;
			if (c == 'X') R[i][j] = -1, J[i][j] = -1;
		}
	}

	BF(x1, y1, R);
	BF(x2, y2, J);

	for (i = 1; i <= N; i ++) {
		for (j = 1; j <= N; j ++) {
			if (J[i][j] != INF) printf("%d ", J[i][j]);
			else printf("INF ");
		}
		printf("\n");
	}

	int tmin = INF, x = 0, y = 0;

	for (i = 1; i <= N; i ++) {
		for (j = 1; j <= M; j ++) {
			if (R[i][j] == J[i][j] && R[i][j] != -1 && R[i][j] < tmin) {
				tmin = R[i][j];
				x = i;
				y = j;
			}
		}
	}

	printf("%d %d %d\n", tmin + 1, x, y);

	return 0;
}