Cod sursa(job #641535)

Utilizator sebii_cSebastian Claici sebii_c Data 28 noiembrie 2011 19:27:21
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 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;

void bf(pair<int, int> p, int r[][NMAX + 10])
{
	int x, y, posx, posy;
	Q.push(p);
	r[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 (r[posx][posy] < 0x3f3f3f3f)
				continue;
			
			r[posx][posy] = r[x][y] + 1;
			Q.push(make_pair(posx, posy));
		}
	}
}

int main()
{
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	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]);
		getchar();
	}

	memset(res, 0x3f, sizeof(res));
	memset(res2, 0x3f, sizeof(res2));
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j) {
			if (A[i][j] == 'R') 
				bf(make_pair(i, j), res);
			else if (A[i][j] == 'J')
				bf(make_pair(i, j), res2);
		}
	
	pair<int, int> p;
	int lenMin = 1000000;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (A[i][j] != 'X' && (res[i][j] == res2[i][j]) && (res[i][j] < lenMin)) {
				lenMin = res[i][j];
				p = make_pair(i, j);
			}

	printf("%d %d %d\n", lenMin, p.first + 1, p.second + 1);
	return 0;
}