Cod sursa(job #2444082)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 30 iulie 2019 12:17:36
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <string>
#include <chrono>

using namespace std;

#include <fstream>
ifstream cin("rj.in"); ofstream cout("rj.out");

int di[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dj[] = { -1, 0, 1, 1, -1, -1, 0, 1 };
bool copaci[105][105];
int teren[2][105][105];
int n, m;
queue < pair < int, int > > q;

void lee(pair <int, int> caracter, int tip) {
	q.push(caracter);
	teren[tip][caracter.first][caracter.second] = 0;

	while (!q.empty()) {
		pair <int, int> now = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int x = now.first + di[i];
			int y = now.second + dj[i];
			if (x < 1 || y < 1 || x > n || y > m) {
				continue;
			}
			if (copaci[x][y]) {
				continue;
			}
			if (teren[tip][x][y] <= teren[tip][now.first][now.second] + 1) {
				continue;
			}
			teren[tip][x][y] = teren[tip][now.first][now.second] + 1;
			q.push({ x, y });
		}
	}

}

int main() {
	cin >> n >> m;
	string carari;

	getline(cin, carari);
	pair <int, int > R, J;

	for (int i = 1; i <= n; i++) {
		getline(cin, carari);
		for (int j = 0; j < m; j++) {
			getline(cin, carari);
			if (carari[j] == 'R') {
				R = { i, j + 1 };
			}
			if (carari[j] == 'J') {
				J = { i, j + 1 };
			}
			if (carari[j] == 'X') {
				copaci[i][j + 1] = true;
			}
			teren[0][i][j + 1] = 1e9;
			teren[1][i][j + 1] = 1e9;
		}
	}

	lee(J, 0);
	lee(R, 1);

	pair <int, int> rasp;
	int MIN = 1e9;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (teren[0][i][j] == teren[1][i][j] && MIN > teren[0][i][j]) {
				rasp = { i, j };
				MIN = teren[0][i][j];
			}
		}
	}
	cout << MIN+1 << " " << rasp.first << " " << rasp.second << "\n";

	return 0;
}