Cod sursa(job #2668507)

Utilizator ihorvaldsTudor Croitoru ihorvalds Data 4 noiembrie 2020 23:03:37
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.25 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, halfway;
char s[101];
vector<vector<int>> mat(101, vector<int>(101)), visited(101, vector<int>(101, 0));
//vector<pair<int, int>> possible_locations;
pair<int, int> romeo_location, juliett_location;
queue<pair<int, int>> q;

inline void getAdjacency(vector<pair<int, int>>& adj, pair<int, int>& cell) {
	int left = cell.first - 1;
	int right = cell.first + 1;
	int up = cell.second - 1;
	int down = cell.second + 1;

	if (0 <= left && left < n && 0 <= cell.second && cell.second < m && mat[left][cell.second] != -1) {
		adj.push_back({ left, cell.second });
	}
	if (0 <= right && right < n && 0 <= cell.second && cell.second < m && mat[right][cell.second] != -1) {
		adj.push_back({ right, cell.second });
	}
	if (0 <= cell.first && cell.first < n && 0 <= up && up < m && mat[cell.first][up] != -1) {
		adj.push_back({ cell.first, up });
	}
	if (0 <= cell.first && cell.first < n && 0 <= down && down < m && mat[cell.first][down] != -1) {
		adj.push_back({ cell.first, down });
	}

	if (0 <= left && left < n && 0 <= up && up < m && mat[left][up] != -1) {
		adj.push_back({ left, up });
	}

	if (0 <= left && left < n && 0 <= down && down < m && mat[left][down] != -1) {
		adj.push_back({ left, down });
	}

	if (0 <= right && right < n && 0 <= up && up < m && mat[right][up] != -1) {
		adj.push_back({ right, up });
	}

	if (0 <= right && right < n && 0 <= down && down < m && mat[right][down] != -1) {
		adj.push_back({ right, down });
	}
}

inline void bfs() {
	while (!q.empty()) {
		pair<int, int> currentCell = q.front();
		q.pop();
		int x = currentCell.first;
		int y = currentCell.second;
		vector<pair<int, int>> adj;
		getAdjacency(adj, currentCell);

		for (const auto& c : adj) {
			if (visited[c.first][c.second] == 0) {
				visited[c.first][c.second] = 1;
				mat[c.first][c.second] = mat[x][y] + 1;
				q.push(c);
			}
			else if (visited[c.first][c.second] == 1000) {
				mat[c.first][c.second] = mat[x][y] + 1;
				halfway = mat[c.first][c.second] / 2;
				return;
			}
		}
	}
}

inline void reconstruct() {
	pair<int, int> currentLocation = juliett_location;
	while (mat[currentLocation.first][currentLocation.second] != halfway) {
		vector<pair<int, int>> adj;
		getAdjacency(adj, currentLocation);
		for (const auto& c : adj) {
			if (mat[c.first][c.second] == mat[currentLocation.first][currentLocation.second] - 1) {
				currentLocation = c;
				break;
			}
		}
	}
	juliett_location = currentLocation;
}

int main()
{
	ifstream in("rj.in");
	ofstream out("rj.out");
	in >> n >> m;
	in.ignore();
	for (int i = 0; i < n; ++i) {
		//fgets_s(s, m);
		in.getline(s, m+1);
		for (int j = 0; j < m; ++j) {
			if (s[j] == 'X') {
				mat[i][j] = -1;
			}
			if (s[j] == 'R') {
				mat[i][j] = 0;
				visited[i][j] = 1;
				romeo_location = { i, j };
				q.push(romeo_location);
			}
			if (s[j] == 'J') {
				mat[i][j] = 0;
				visited[i][j] = 1000;
				juliett_location = { i, j };
			}
		}
	}

	bfs();

	reconstruct();


	int x = juliett_location.first;
	int y = juliett_location.second;
	out << x+1 << " " << y+1 << " " << mat[x][y];
}