Cod sursa(job #641530)

Utilizator sebii_cSebastian Claici sebii_c Data 28 noiembrie 2011 18:59:31
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>

#define NMAX 100

using namespace std;

int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
int res[NMAX + 10][NMAX + 10], res2[NMAX + 10][NMAX + 10];
char A[NMAX + 10][NMAX + 10];
queue< pair<int, int> > Q;
int n, m, lenMin = 100000;

void bf(pair<int, int> p)
{
	int x, y, posx, posy;
	Q.push(p);
	res[p.first][p.second] = 1;
	while (!Q.empty()) {
		x = Q.front().first;
		y = Q.front().second;
		Q.pop();
		for (int i = 0; i < 8; ++i) {
			posx = x + dx[i];
			posy = y + dy[i];

			if (posx < 0 || posx >= n || posy < 0 || posy >= m)
				continue;
			if (A[posx][posy] == 'X')
				continue;
			if (res[posx][posy])
				continue;
			
			res[posx][posy] = res[x][y] + 1;
			Q.push(make_pair(posx, posy));
		}
	}
}

pair<int, int> bf2(pair<int, int> p)
{
	int x, y, posx, posy;
	pair<int, int> pos = make_pair(1000, 1000);
	res2[p.first][p.second] = 1;
	Q.push(p);
	while (!Q.empty()) {
		x = Q.front().first;
		y = Q.front().second;
		Q.pop();
		if (res[x][y] == res2[x][y]) {
			if (res[x][y] < lenMin) {
				lenMin = res[x][y];
				pos = make_pair(x, y);
			}
			else if (res[x][y] == lenMin && x < pos.first) 
				pos = make_pair(x, y);
			else if (res[x][y] == lenMin && x == pos.first && y < pos.first)
				pos = make_pair(x, y);
		}

		for (int i = 0; i < 8; ++i) {
			posx = x + dx[i];
			posy = y + dy[i];

			if (posx < 0 || posx >= n || posy < 0 || posy >= m)
				continue;
			if (A[posx][posy] == 'X')
				continue;
			if (res2[posx][posy])
				continue;
			
			res2[posx][posy] = res2[x][y] + 1;
			Q.push(make_pair(posx, posy));
		}
	}
	return pos;
}

int main()
{
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	vector< pair<int, int> > pr;
	scanf("%d %d\n", &n, &m);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			scanf("%c", &A[i][j]);
			if (A[i][j] == 'R' || A[i][j] == 'J') {
				pr.push_back(make_pair(i, j));
			}
		}
		getchar();
	}

	bf(pr[0]);
	pair<int, int> p = bf2(pr[1]);
	printf("%d %d %d", lenMin, p.first + 1, p.second + 1);
	return 0;
}