Cod sursa(job #1370470)

Utilizator vladrochianVlad Rochian vladrochian Data 3 martie 2015 14:54:24
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <queue>
using namespace std;

const int kMaxN = 105, kInf = 0x3f3f3f3f;
const int dx[] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dy[] = {1, 1, 1, 0, -1, -1, -1, 0};

ifstream fin("rj.in");
ofstream fout("rj.out");

int N, M;
char a[kMaxN][kMaxN];
int dr[kMaxN][kMaxN], dj[kMaxN][kMaxN];
int rx, ry, jx, jy;
int tmin = kInf, bestx, besty;

void BFS(int dist[kMaxN][kMaxN], int stx, int sty) {
	queue<pair<int, int>> q;
	dist[stx][sty] = 1;
	q.push(make_pair(stx, sty));
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 8; ++i) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (a[nx][ny] == ' ' && !dist[nx][ny]) {
				dist[nx][ny] = dist[x][y] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}
}

int main() {
	fin >> N >> M;
	fin.ignore(1);
	for (int i = 1; i <= N; ++i) {
		fin.getline(a[i] + 1, M + 3);
		for (int j = 1; j <= M; ++j)
			if (a[i][j] == 'R') {
				rx = i;
				ry = j;
			} else if (a[i][j] == 'J') {
				jx = i;
				jy = j;
			}
	}
	BFS(dr, rx, ry);
	BFS(dj, jx, jy);
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			if (dr[i][j] && dr[i][j] == dj[i][j] && dr[i][j] < tmin) {
				tmin = dr[i][j];
				bestx = i;
				besty = j;
			}
	fout << tmin << " " << bestx << " " << besty << "\n";
	return 0;
}