Cod sursa(job #2170256)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 14 martie 2018 23:02:32
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <algorithm>
#include <queue>

#include <cstdio>
#include <cstring>

#define x first
#define y second
using namespace std;

using pii = pair<int, int>;

const int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

const int N = 105, INF = 0x3f3f3f3f;


char mx[N][N];
int dr[N][N], dj[N][N];

int n, m, sx, sy, ex, ey;


static bool ok(int x, int y) {
	return (1 <= x && x <= n) && (1 <= y && y <= m); }

static void bfs(int x, int y, int dist[N][N]) {
	deque<pii> dq;
	int nx, ny;

	memset(dist, 0x3f, sizeof(int) * N * N);
	dist[x][y] = 0;
	dq.emplace_back(x, y);

	while (!dq.empty()) {
		pii u = dq.front(); dq.pop_front();
		x = u.x, y = u.y;

		for (int dir = 0; dir < 8; ++dir) {
			nx = x + dx[dir], ny = y + dy[dir];
			if (ok(nx, ny) && mx[nx][ny] != 'X' && dist[nx][ny] == INF) {
				dist[nx][ny] = dist[x][y] + 1;
				dq.emplace_back(nx, ny); } } } }

static char getget() {
	char ch;
	do {
		ch = getchar(); }
	while (!(ch == ' ' || ch == 'R' || ch == 'J' || ch == 'X'));
	return ch; }

static void slut() {
	char ch;
	do {
		ch = getchar(); }
	while (!(ch == '\n' || ch == EOF)); }

int main() {
	freopen("rj.in", "r", stdin);
	freopen("rj.out", "w", stdout);
	int ant, x, y;
	char ch;

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j)
			mx[i][j] = getget();
		slut(); }

	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
		switch (mx[i][j]) {
		case 'R': {
			sx = i, sy = j;
			break; }
		case 'J': {
			ex = i, ey = j;
			break; } }

	bfs(sx, sy, dr);
	bfs(ex, ey, dj);

	ant = 2e9;
	for (int i = 1; i <= n; ++i)
	for (int j = 1; j <= m; ++j)
		if (max(dr[i][j], dj[i][j]) < ant) {
			ant = max(dr[i][j], dj[i][j]);
			x = i, y = j; }

	printf("%d %d %d\n", ++ant, x, y);

	return 0; }