Pagini recente » Cod sursa (job #588419) | Cod sursa (job #1123059) | Borderou de evaluare (job #593669) | Cod sursa (job #768158) | Cod sursa (job #1982688)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
typedef vector<string> Harta;
typedef vector<vector<int>> Distante;
struct Coord {
Coord(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
int x, y;
};
template<typename T>
void initMatrice(int lin, int col, T& matrice)
{
matrice.resize(lin);
for (auto& it : matrice) {
it.resize(col);
}
}
void bf(const Coord &start, const Harta &harta, Distante &dist)
{
queue<Coord> q;
q.push(start);
int n = harta.size();
int m = harta[0].size();
while (!q.empty()) {
Coord pos = q.front();
q.pop();
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i == 0 && j == 0) {
continue;
}
int x = pos.x + j;
int y = pos.y + i;
if (x >= 0 && x < m && y >= 0 && y < n) {
if (harta[y][x] != 'X') {
if (dist[y][x] == 0 && (x != start.x || y != start.y)) {
dist[y][x] = dist[pos.y][pos.x] + 1;
q.push(Coord(x, y));
}
}
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
ifstream fin("rj.in");
ofstream fout("rj.out");
int n, m;
fin >> n >> m;
fin.get();
Coord startR, startJ;
Harta harta(n);
for (int i = 0; i < n; i++) {
string line;
getline(fin, line);
harta[i] = line;
for (int j = 0; j < m; j++) {
if (harta[i][j] == 'R') {
startR = Coord(j, i);
} else if (harta[i][j] == 'J') {
startJ = Coord(j, i);
}
}
}
Distante distR, distJ;
initMatrice(n, m, distR);
initMatrice(n, m, distJ);
bf(startR, harta, distR);
bf(startJ, harta, distJ);
Coord posMin(-1, -1);
int distMin = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (distR[i][j] == 0) {
continue;
}
if (distR[i][j] == distJ[i][j]) {
int dist = distR[i][j];
if ((posMin.x == -1 && posMin.y == -1)
|| (distMin > dist)
|| ((distMin == dist) && ((i < posMin.y || (i == posMin.y && j < posMin.x))))) {
posMin = Coord(j, i);
distMin = dist;
}
}
}
}
fout << distMin + 1<< " " << posMin.y + 1<< " " << posMin.x + 1;
fin.close();
fout.close();
return 0;
}