Pagini recente » Cod sursa (job #2191796) | Cod sursa (job #2655882) | Cod sursa (job #1732496) | Borderou de evaluare (job #1978045) | Cod sursa (job #2668526)
#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>> romeo_map(101, vector<int>(101)), juliett_map(101, vector<int>(101)), visited(101, vector<int>(101, 0));
pair<int, int> romeo_location, juliett_location, location;
queue<pair<int, int>> q;
inline void getAdjacency(vector<vector<int>>& mat, 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(vector<vector<int>>& mat, pair<int, int>& pos, int seeker) {
q.push(pos);
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(mat, adj, currentCell);
for (const auto& c : adj) {
if (visited[c.first][c.second] != seeker) {
visited[c.first][c.second] = seeker;
mat[c.first][c.second] = mat[x][y] + 1;
q.push(c);
}
}
}
}
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') {
romeo_map[i][j] = -1;
juliett_map[i][j] = -1;
}
if (s[j] == 'R') {
romeo_map[i][j] = 1;
juliett_map[i][j] = 0;
visited[i][j] = 1;
romeo_location = { i, j };
}
if (s[j] == 'J') {
romeo_map[i][j] = 0;
juliett_map[i][j] = 1;
visited[i][j] = 2;
juliett_location = { i, j };
}
}
}
bfs(romeo_map, romeo_location, 1);
bfs(juliett_map, juliett_location, 2);
int minimum = (int)1e4;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (romeo_map[i][j] == juliett_map[i][j] && visited[i][j] != 0) {
if (romeo_map[i][j] < minimum) {
location = { i, j };
minimum = romeo_map[i][j];
}
}
}
}
out << minimum << " " << location.first + 1 << " " << location.second + 1;
}