Cod sursa(job #130589)

Utilizator tvladTataranu Vlad tvlad Data 1 februarie 2008 15:51:33
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#include <queue>
using namespace std;

struct punct { int x,y; };

const int N = 100;
const int M = 100;
const int ND = 8;
const punct d[ND] = { {-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} };

int n,m, rx,ry, jx,jy;
bool ok[N][M];
int dr[N][M];
int dj[N][M];
char s[M];

void bf ( int sx, int sy, int a[][M] ) {
	punct cur = {sx,sy};
	a[sx][sy] = 1;
	queue<punct> q;
	for (q.push(cur); !q.empty();) {
		cur = q.front(); q.pop();
		for (int i = 0; i < ND; ++i) {
			punct next = {cur.x + d[i].x, cur.y + d[i].y};
			if (0 <= next.x && next.x < n && 0 <= next.y && next.y < m && ok[next.x][next.y] && a[next.x][next.y] == 0) {
				a[next.x][next.y] = a[cur.x][cur.y]+1;
				q.push(next);
			}
		}
	}
}

int main() {
	freopen("rj.in","rt",stdin);
	freopen("rj.out","wt",stdout);
	scanf("%d %d\n",&n,&m);
	for (int i = 0; i < n; ++i) {
		fgets(s,100,stdin);
		for (int j = 0; j < m; ++j) {
			switch (s[j]) {
				case 'R':rx = i; ry = j; ok[i][j] = true; break;
				case 'J':jx = i; jy = j; ok[i][j] = true; break;
				case 'X':ok[i][j] = false; break;
				case '\0':for (;;);
				default:ok[i][j] = true;
			}
		}
	}

	bf(rx,ry,dr);
	bf(jx,jy,dj);

	int min = 0x3f3f3f3f, mx, my;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (dr[i][j] > 0 && dr[i][j] == dj[i][j] && dr[i][j] < min) {
				min = dr[i][j];
				mx = i;
				my = j;
			}
		}
	}
	printf("%d %d %d\n",min,mx+1,my+1);
	return 0;
}