Cod sursa(job #704725)

Utilizator silviuboganSilviu Bogan silviubogan Data 2 martie 2012 19:52:35
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <cstdio>
using namespace std;

#define MAX_DIM 200

int N, M, hr[MAX_DIM][MAX_DIM], hj[MAX_DIM][MAX_DIM], xr, yr, xj, yj, xf = 0, yf = 0, d,
	dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct pos { int x, y; };

void lee (int h[MAX_DIM][MAX_DIM], int x, int y) {
	int lc = 1;
	pos c[MAX_DIM * 10];

	c[1].x = x;
	c[1].y = y;
	
	while (lc != 0) {
		pos t = {c[lc].x, c[lc].y}, p;
		lc--;

		for (int i = 0; i < 8; i++) {
			p.x = t.x + dx[i];
			p.y = t.y + dy[i];
			int dp = h[p.x][p.y], dt = h[t.x][t.y];
			if (dp == 0 || (dt + 1 < dp)) {
				lc++;
				c[lc] = p;
				h[p.x][p.y] = dt + 1;
			}
		}
	}
}

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

	scanf("%d %d", &N, &M);
	d = N * N;

	char c;
	for (int i = 1; i <= N; i++) {
		scanf("%*c");
		for (int j = 1; j <= M; j++) {
			scanf("%c", &c);
			if (c == 'R') {
				xr = i;
				yr = j;
				hr[i][j] = 1;
				hj[i][j] = 0;
			} else if (c == 'J') {
				xj = i;
				yj = j;
				hr[i][j] = 0;
				hj[i][j] = 1;
			} else if (c == 'X') {
				hr[i][j] = hj[i][j] = -1;
			} else {
				hr[i][j] = hj[i][j] = 0;
			}
		}
	}

	for (int i = 0; i <= N + 1; i++) {
		hr[i][0] = hr[i][M + 1] = hj[i][0] = hj[i][M + 1] = -1;
	}
	for (int i = 0; i <= M + 1; i++) {
		hr[0][i] = hr[N + 1][i] = hj[0][i] = hj[N + 1][i] = -1;
	}

	lee(hr, xr, yr);
	lee(hj, xj, yj);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (hr[i][j] == hj[i][j] && 0 < hr[i][j] && hr[i][j] < d) {
				d = hr[i][j];
				xf = i;
				yf = j;
			}
		}
	}
	printf("%d %d %d\n", d, xf, yf);
	
	return 0;
}