Cod sursa(job #2170295)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 14 martie 2018 23:18:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 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 N = 105, INF = 0x3f3f3f3f;


char mx[N][N];
int dr[N][N], dj[N][N], dx[8], dy[8];

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, pt;
	char ch;

	scanf("%d%d", &n, &m);
	slut();
	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; } }

	pt = 0;
	for (int x = -1; x <= +1; ++x)
	for (int y = -1; y <= +1; ++y) if (x || y) {
		dx[pt] = x;
		dy[pt] = y;
		pt+= 1; }

	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 (mx[i][j] != 'X' && dr[i][j] == dj[i][j] && dr[i][j] < ant) {
			ant = dr[i][j];
			x = i, y = j; }

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

	return 0; }