Cod sursa(job #2236249)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 28 august 2018 20:52:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("rj.in");
ofstream g ("rj.out");

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

const int NMAX = 100;
string a[NMAX];
short dist[NMAX][NMAX];
bool vis[NMAX][NMAX];
int n, m, x, y, cost, nx, ny, ans;
queue < pair <pii, int> > q;
pair <pii, int> p;
pii p0, p1, sol;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef LOCAL_DEFINE
	freopen (".in", "r", stdin);
#endif
	f >> n >> m;
	getline (f, a[0]);
	for (int i = 0; i < n; ++i) {
        getline (f, a[i]);
		for (int j = 0; j < m; ++j) {
            dist[i][j] = -1;
			if (a[i][j] == 'R') {
				p0 = {i, j};
			} else if (a[i][j] == 'J') {
				p1 = {i, j};
			}
		}
	}

	q.push ({p0, 1});

	while (!q.empty()) {
		p = q.front();
		q.pop();

		x = p.fi.fi;
		y = p.fi.se;
		cost = p.se;

		if (dist[x][y] != -1) {
			continue;
		}

		dist[x][y] = cost;

		for (int dir = 0; dir < 8; ++dir) {
			nx = x + dx[dir];
			ny = y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m || dist[nx][ny] != -1 || a[nx][ny] == 'X') continue;

			q.push ({{nx, ny}, cost + 1});
		}
	}

	q.push ({p1, 1});

    ans = 1 << 30;
	while (!q.empty()) {
		p = q.front();
		q.pop();

		x = p.fi.fi;
		y = p.fi.se;
		cost = p.se;

		if (vis[x][y]) {
			continue;
		}

		vis[x][y] = true;

		if (dist[x][y] == cost) {
			if (ans > cost) {
				ans = cost;
				sol = {x, y};
			} else if (ans == cost && (sol.fi > x || (sol.fi == x && sol.se > y))) {
				sol = {x, y};
			}
		}

		for (int dir = 0; dir < 8; ++dir) {
			nx = x + dx[dir];
			ny = y + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || a[nx][ny] == 'X') continue;

			q.push ({{nx, ny}, cost + 1});
		}
	}

	g << ans << ' ' << sol.fi + 1 << ' ' << sol.se + 1 << '\n';

	f.close();
	g.close();
	return 0;
}