Pagini recente » Cod sursa (job #1574969) | Cod sursa (job #453318) | Cod sursa (job #107987) | Cod sursa (job #2071424) | Cod sursa (job #876870)
Cod sursa(job #876870)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int MAX_N = 105;
const int INF = 1 << 30;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int N, M;
int romeo[MAX_N][MAX_N];
int juliet[MAX_N][MAX_N];
pair<int, int> romeo_start;
pair<int, int> juliet_start;
int sol_dist = INF, sol_x = 0, sol_y = 0;
void read_input();
void solve();
void write_output();
void bfs(int mat[MAX_N][MAX_N], pair<int, int> start);
bool in_bounds(int x, int y);
int main() {
read_input();
solve();
write_output();
return 0;
}
void read_input() {
fin >> N >> M;
fin.ignore();
string row;
for (int i = 1; i <= N; ++i) {
getline(fin, row);
for (int j = 0; j < M; ++j) {
if (row[j] == 'X') {
romeo[i][j+1] = juliet[i][j+1] = -1;
} else if (row[j] == 'R') {
romeo[i][j+1] = 0;
juliet[i][j+1] = INF;
romeo_start.first = i;
romeo_start.second = j + 1;
} else if (row[j] == 'J') {
juliet[i][j+1] = 0;
romeo[i][j+1] = INF;
juliet_start.first = i;
juliet_start.second = j + 1;
} else {
romeo[i][j+1] = juliet[i][j+1] = INF;
}
}
}
}
void solve() {
bfs(romeo, romeo_start);
bfs(juliet, juliet_start);
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= M; ++j) {
if (romeo[i][j] != -1 && romeo[i][j] == juliet[i][j]) {
if (romeo[i][j] < sol_dist) {
sol_dist = romeo[i][j];
sol_x = i;
sol_y = j;
}
}
}
}
}
void bfs(int mat[MAX_N][MAX_N], pair<int, int> start) {
queue<pair<int, int> > q;
q.push(start);
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
for (int k = 0; k < 4; ++k) {
int xx = x + dx[k], yy = y + dy[k];
if (in_bounds(xx, yy) && mat[xx][yy] >= 0) {
if (mat[x][y] + 1 < mat[xx][yy]) {
mat[xx][yy] = mat[x][y] + 1;
q.push(make_pair(xx, yy));
}
}
}
q.pop();
}
}
inline bool in_bounds(int x, int y) {
if (x < 1 || x > N) return false;
if (y < 1 || y > M) return false;
return true;
}
void write_output() {
fout << sol_dist << ' ' << sol_x << ' ' << sol_y;
}