Cod sursa(job #674138)

Utilizator silviuboganSilviu Bogan silviubogan Data 5 februarie 2012 17:26:29
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
using namespace std;

int n, m, kmin, dc[8] = {0, 1, 1, 1, 0, -1, -1, -1},
	dl[8] = {1, 1, 0, -1, -1, -1, 0, 1}, l;
char h[100][100];
struct pos { int l, c; } rp, jp, sol[10], cp, solf[10];
bool fsol = true;

inline bool valid (int k) {
	if (fsol || k <= kmin) {
		if (sol[k].l >= 0 && sol[k].l < n &&
			sol[k].c >= 0 && sol[k].c < m &&
			h[sol[k].l][sol[k].c] != 'X') {
				for (int i = 0; i < k; i++) {
					if (sol[i].l == sol[k].l &&
						sol[i].c == sol[k].c) {
							return false;
					}
				}
				return true;
		}
	}
	return false;
}

inline bool solutie (int k) {
	return k % 2 == 0 && sol[k].l == jp.l && sol[k].c == jp.c;
}

void b (int k) {
	for (int i = 0; i < 8; i++) {
		sol[k].l = sol[k - 1].l + dl[i];
		sol[k].c = sol[k - 1].c + dc[i];

		if (valid(k)) {
			if (solutie(k)) {
				if (fsol) {
					kmin = k;
					fsol = false;
				} else if (k < kmin) {
					kmin = k;
				}
				l = k + 1;
				for (int i = 0; i < l; i++) {
					solf[i] = sol[i];
				}
			} else {
				b(k + 1);
			}
		}
	}
}

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

	scanf("%d %d%*c", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%c", &h[i][j]);
			if (h[i][j] == 'R') {
				rp.l = i;
				rp.c = j;
			} else if (h[i][j] == 'J') {
				jp.l = i;
				jp.c = j;
			}
		}
		scanf("%*c");
	}

	sol[0].l = rp.l;
	sol[0].c = rp.c;
	b(1);

	printf("%d %d %d\n", l / 2 + 1, solf[l / 2].l + 1, solf[l / 2].c + 1);

	return 0;
}