Pagini recente » Cod sursa (job #2728638) | Cod sursa (job #2470882) | Cod sursa (job #2985976) | Cod sursa (job #3250319) | Cod sursa (job #1619093)
#include <fstream>
#include <queue>
#include <algorithm>
#define nmax 105
#define big 10005
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n, m, map_romeo[nmax][nmax], map_juliette[nmax][nmax], time[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, r_1, r_2, r_3, min_time = big;
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);
if (x.size() != 0)
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]]) {
time[x + d_x[k]][y + d_y[k]] = map_juliette[x + d_x[k]][y + d_y[k]];
min_time = min(min_time, time[x + d_x[k]][y + d_y[k]]);
}
tail.push(make_pair(x + d_x[k], y + d_y[k]));
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (time[i][j] == min_time) {
fout << time[i][j] << " " << i << " " << j;
return 0;
}
}