Cod sursa(job #757236)

Utilizator Victor10Oltean Victor Victor10 Data 11 iunie 2012 15:44:30
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <queue>
#include <utility>
#define x first
#define y second
#define DM 105
using namespace std;
typedef pair <int, int> per;

int dstromeo [DM] [DM], dstjulieta [DM] [DM];
int n, m;
int dx [] = {0, 1, 1, 1, 0, -1, -1, -1}, dy [] = {-1, -1, 0, 1, 1, 1, 0, -1};
char s [DM];
per rstart, jstart, answ;

bool check (int i, int j) {
	return !( i < 0 || i >= n || j < 0 || j >= m);
}

void lee (int mat [DM] [DM], per start) {
	int d, ii, jj;
	queue <per> c;
	per fr;
	for (c . push (start); c . size (); c . pop ()) {
		fr = c . front ();
		for (d = 0; d < 8; ++ d) {
			ii = fr . x + dx [d]; jj = fr . y + dy [d];
			if (check (ii, jj) && mat [ii] [jj] == -1) {
				mat [ii] [jj] = mat [fr . x] [fr .y] + 1;
				c . push (make_pair (ii, jj));
			}
		}
	}
}


int main () {
	
	freopen ("rj.in", "r", stdin);
	freopen ("rj.out", "w", stdout);
	
	int i, j, minn = 10000;
	
	scanf ("%d%d\n", &n, &m);
	for (i = 0; i < n; ++ i) {
		fgets (s, 105, stdin);
		for (j = 0; j < m; ++ j) {
			if (s [j] == 'R') {
				rstart = make_pair (i, j);
				dstromeo [i] [j] = 1;
				dstjulieta [i] [j] = -2; 
			}
			if (s [j] == 'J') {
				jstart = make_pair (i, j);
				dstjulieta [i] [j] = 1;
				dstromeo [i] [j] = -2;
			}
			if (s [j] == ' ') {
				dstromeo [i] [j] = -1;
				dstjulieta [i] [j] = -1;
			}
			if (s [j] == 'X') {
				dstromeo [i] [j] = -2;
				dstjulieta [i] [j] = -2;
			}
		}
	}
	
	lee (dstromeo, rstart);
	lee (dstjulieta, jstart);

	for (i = 0; i < n; ++ i) {
		for (j = 0; j < n; ++ j) {
			if (dstromeo [i] [j] == dstjulieta [i] [j] && dstromeo [i] [j] < minn && dstromeo [i] [j] > 0) {
				minn = dstromeo [i] [j];
				answ = make_pair (i, j);
			}
		}
	}
	
	printf ("%d %d %d\n", minn, answ . x + 1, answ . y + 1);
}