Pagini recente » Cod sursa (job #712149) | Cod sursa (job #3209972) | Cod sursa (job #3286090) | Cod sursa (job #3237454) | Cod sursa (job #1617489)
#include <fstream>
#include <queue>
#define nmax 105
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n, m, map_romeo[nmax][nmax], map_juliette[nmax][nmax];
queue < pair < int, int > > tail;
bool is_ok(int x, int y) {
if (x < 1 or y < 1 or x > n or y > m or map_romeo[x][y] != 0)
return false;
return true;
}
bool is_ok_s(int x, int y) {
if (x < 1 or y < 1 or x > n or y > m or map_juliette[x][y] != 0)
return false;
return true;
}
int main()
{
int r_x, r_y, j_x, j_y, min_time = 10005, r_1, r_2, r_3;
int d_x[8] = {-1, 0, 1, 0, 1, 1, -1, -1};
int d_y[8] = {0, 1, 0, -1, 1, -1, -1, 1};
fin >> n >> m;
fin.get();
for (int i = 1; i <= n; ++i) {
string x;
getline(fin, x);
for (int j = 0; j <= x.size() - 1; ++j) {
(x[j] == 'R')? r_x = i, r_y = j + 1, map_romeo[r_x][r_y] = 1: true;
(x[j] == 'J')? j_x = i, j_y = j + 1, map_juliette[j_x][j_y] = 1: true;
(x[j] == 'X')? map_romeo[i][j + 1] = -1, map_juliette[i][j + 1] = -1: true;
}
}
tail.push(make_pair(r_x, r_y));
while (!tail.empty()) {
int x = tail.front().first;
int y = tail.front().second;
tail.pop();
for (int k = 0; k <= 7; ++k)
if (is_ok(x + d_x[k], y + d_y[k])) {
map_romeo[x + d_x[k]][y + d_y[k]] = map_romeo[x][y] + 1;
tail.push(make_pair(x + d_x[k], y + d_y[k]));
}
}
tail.push(make_pair(j_x, j_y));
while (!tail.empty()) {
int x = tail.front().first;
int y = tail.front().second;
tail.pop();
for (int k = 0; k <= 7; ++k)
if (is_ok_s(x + d_x[k], y + d_y[k])) {
map_juliette[x + d_x[k]][y + d_y[k]] = map_juliette[x][y] + 1;
if (map_juliette[x + d_x[k]][y + d_y[k]] == map_romeo[x + d_x[k]][y + d_y[k]] and min_time > map_juliette[x + d_x[k]][y + d_y[k]]) {
r_1 = map_juliette[x + d_x[k]][y + d_y[k]];
r_2 = x + d_x[k];
r_3 = y + d_y[k];
min_time = map_juliette[x + d_x[k]][y + d_y[k]];
}
tail.push(make_pair(x + d_x[k], y + d_y[k]));
}
}
fout << r_1 << " " << r_2 << " " << r_3;
}