Cod sursa(job #97038)

Utilizator tvladTataranu Vlad tvlad Data 4 noiembrie 2007 19:12:17
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <cstdlib>

struct punct { int x,y; };

const int ND = 4;
const punct D[ND] = { {0,1}, {1,0}, {0,-1}, {-1,0} };
const int N = 5; // de schimbat in 100!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

int n,m;
bool a[N][N];
int dr[N][N], dj[N][N];

void bf ( punct s, int d[N][N] ) {
	punct* q = new punct[n*m];
	int st = 0, fi = -1;
	d[s.x][s.y] = 0;
	for (q[++fi] = s; st <= fi; ++st) {
		for (int k = 0; k < ND; ++k) {
			punct nx = { q[st].x+D[k].x, q[st].y+D[k].y };
			if (0 <= nx.x && nx.x < n && 0 <= nx.y && nx.y < m && a[nx.x][nx.y] && d[nx.x][nx.y] == 0 && (nx.x != s.x || nx.y != s.y)) {
				d[nx.x][nx.y] = d[q[st].x][q[st].y]+1;
				q[++fi] = nx;
			}
		}
	}
}

int main() {
	freopen("rj.in","rt",stdin);
	freopen("rj.out","wt",stdout);
	scanf("%d %d\n",&n,&m);
	char c;
	punct rom,jul;
	for (int i = 0; i<n; ++i) {
		for (int j = 0; j<m; ++j) {
			scanf("%c",&c);
			switch (c) {
				case 'R':a[i][j] = true; rom.x = i; rom.y = j; break;
				case 'J':a[i][j] = true; jul.x = i; jul.y = j; break;
				case 'X':a[i][j] = false; break;
				default:a[i][j] = true;
			}
		}
		scanf("\n");
	}
	bf(rom,dr);
	bf(jul,dj);
	int min = 0x3f3f3f3f, pi, pj;
	for (int i = 0; i<n; ++i) {
		for (int j = 0; j<m; ++j) {
			if (dr[i][j] == dj[i][j] && dr[i][j] != 0 && dr[i][j] < min) {
				min = dr[i][j];
				pi = i;
				pj = j;
			}
		}
	}
	printf("%d %d %d\n",min,pi+1,pj+1);
	return 0;
}