Pagini recente » Cod sursa (job #1334463) | Cod sursa (job #3192321) | Cod sursa (job #842694) | Cod sursa (job #1110152) | Cod sursa (job #2663979)
#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <queue>
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
class Graph {
int romeoX, romeoY, julietaX, julietaY, N, M;
vector <vector <int>> romeo, julieta;
vector <int> dirX, dirY;
queue <pair <int, int>> pairs;
public:
Graph(int N, int M) : N(N), M(M), romeo(N, vector <int> (M)), julieta(N, vector <int> (M)), dirX({-1, -1, 1, 1, -1, 0, 1, 0}), dirY({-1, 1, -1, 1, 0, -1, 0, 1}) {
for (int i = 0; i < N; ++i) {
string line;
getline(in, line);
for (int k = 0; k < M; ++k) {
switch(line[k]) {
case 'X':
romeo[i][k] = julieta[i][k] = -1;
break;
case 'R':
romeoX = i;
romeoY = k;
julieta[i][k] = INT_MAX;
break;
case 'J':
julietaX = i;
julietaY = k;
romeo[i][k] = INT_MAX;
break;
default:
romeo[i][k] = julieta[i][k] = INT_MAX;
break;
}
}
}
romeo[romeoX][romeoY] = 0;
julieta[julietaX][julietaY] = 0;
}
bool isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < M;
}
void Lee(vector <vector <int>> &character) {
while (pairs.size()) {
pair <int, int> top = pairs.front();
pairs.pop();
for (int i = 0; i < 8; ++i) {
int dx = dirX[i], dy = dirY[i];
pair <int, int> neighbour = make_pair(top.first + dx, top.second + dy);
if (!isValid(neighbour.first, neighbour.second) || character[neighbour.first][neighbour.second] == -1)
continue;
if (1 + character[top.first][top.second] < character[neighbour.first][neighbour.second]) {
character[neighbour.first][neighbour.second] = 1 + character[top.first][top.second];
pairs.push(neighbour);
}
}
}
}
void solve() {
pairs.push(make_pair(romeoX, romeoY));
Lee(romeo);
pairs.push(make_pair(julietaX, julietaY));
Lee(julieta);
int line = 0, column = 0, minDist = INT_MAX;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j) {
if (romeo[i][j] == julieta[i][j] && romeo[i][j] != -1 && romeo[i][j] < minDist) {
line = i;
column = j;
minDist = romeo[i][j];
}
}
out << minDist + 1 << " " << line + 1 << " " << column + 1;
}
};
int main() {
int N, M;
in >> N >> M;
in.get();
Graph *myGraph = new Graph(N, M);
myGraph -> solve();
in.close();
out.close();
return 0;
}