Pagini recente » Cod sursa (job #578682) | Cod sursa (job #1822065) | Cod sursa (job #2261805) | Cod sursa (job #3174613) | Cod sursa (job #2193435)
#include <cstdio>
#include <queue>
const int MAX_N = 100;
struct Coord {
int x;
int y;
};
int n, m;
char a[1 + MAX_N][5 + MAX_N];
int dist[2][1 + MAX_N][1 + MAX_N];
bool viz[1 + MAX_N][1 + MAX_N];
int dirLin[] = {-1, 1, 0, 0, -1, 1, 1, -1};
int dirCol[] = {0, 0, 1, -1, 1, 1, -1, -1};
void initViz() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
viz[i][j] = false;
}
}
}
bool valid(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m && a[x][y] != 'X';
}
void bfs(int start, int startX, int startY) {
initViz();
std::queue<Coord> q;
q.push({startX, startY});
viz[startX][startY] = true;
dist[start][startX][startY] = 0;
while (!q.empty()) {
Coord front = q.front();
q.pop();
int x = front.x;
int y = front.y;
for (int dir = 0; dir < 8; dir++) {
int newX = x + dirLin[dir];
int newY = y + dirCol[dir];
if (valid(newX, newY) && !viz[newX][newY]) {
q.push({newX, newY});
viz[newX][newY] = true;
dist[start][newX][newY] = dist[start][x][y] + 1;
}
}
}
}
int main() {
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
scanf("%d%d\n", &n, &m);
for (int i = 1; i <= n; i++) {
gets(a[i] + 1);
for (int j = 1; j <= m; j++) {
if (a[i][j] == 'R') {
x1 = i;
y1 = j;
} else if (a[i][j] == 'J') {
x2 = i;
y2 = j;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dist[0][i][j] = -1;
dist[1][i][j] = -1;
}
}
bfs(0, x1, y1);
bfs(1, x2, y2);
int tMin = 2000000000;
int x, y;
x = y = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (dist[0][i][j] != -1 && dist[0][i][j] == dist[1][i][j] && dist[0][i][j] < tMin) {
tMin = dist[0][i][j];
x = i;
y = j;
}
}
}
printf("%d %d %d\n", 1 + tMin, x, y);
return 0;
}