Cod sursa(job #84481)

Utilizator wefgefAndrei Grigorean wefgef Data 15 septembrie 2007 12:59:47
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

#define mp make_pair
#define x first
#define y second

const int Nmax = 128;
const int inf = 1000000000;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

int n, m;
char A[Nmax][Nmax];
int C[Nmax][Nmax][2];
queue< pair<int, int> > Q;

void ReadData() {
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);

	scanf("%d %d\n", &n, &m);
	for (int i = 1; i <= n; ++i) {
		char buf[Nmax];
		fgets(buf, Nmax, stdin);
		for (int j = 1; j <= m; ++j)
			A[i][j] = buf[j-1];
	}
}

void expand(pair<int, int> p, int k) {
	for (int d = 0; d < 4; ++d) {
		int i = p.x + dx[d];
		int j = p.y + dy[d];
		if (i && i <= n && j && j <= m)
			if (A[i][j] != 'X' && !C[i][j][k]) {
				C[i][j][k] = C[p.x][p.y][k] + 1;
				Q.push(mp(i, j));
			}
	}
}

void BFS(pair<int, int> start, int k) {
	C[start.x][start.y][k] = 1;
	Q.push(start);
	while (!Q.empty()) {
		expand(Q.front(), k);
		Q.pop();
	}
}

void Solve() {
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) {
			if (A[i][j] == 'R') BFS(mp(i, j), 0);
			if (A[i][j] == 'J') BFS(mp(i, j), 1);
		}
}

void WriteData() {
	int best = inf;
	pair<int, int> p;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			if (C[i][j][0] > 0 && C[i][j][0] == C[i][j][1] && C[i][j][0] < best) {
				best = C[i][j][0];
				p = mp(i, j);
			}
	printf("%d %d %d\n", best-1, p.x, p.y);
}

int main() {
	ReadData();
	Solve();
	WriteData();
}