社区讨论
80分求助
P2199最后的迷宫参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lowy61o1
- 此快照首次捕获于
- 2023/11/13 21:35 2 年前
- 此快照最后确认于
- 2023/11/14 07:29 2 年前
CPP
#include <cstdio>
#include <string>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
struct node {
int x, y, t;
node() {
}
node(const int &xx, const int &yy, const int &tt) {
x = xx, y = yy, t = tt;
}
};
bool map[5005][5005];
bool vis[5005][5005];
int n, m, walk[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {-1, 1}, {1, -1}};
void seach(const int &x, const int &y, const int &ex, const int &ey);
bool pd(const int &x, const int &y, const int &ex, const int &ey);
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
char temp;
cin >> temp;
map[i][j] = ((temp == 'X') ? false : true);
}
}
int x, y, xx, yy;
while (scanf("%d%d%d%d", &x, &y, &xx, &yy)) {
memset(vis, 0, sizeof(vis));
if (x == 0 && y == 0 && xx == 0 && yy == 0) {
break;
}
if (!map[x][y]) {
printf("Poor Harry\n");
continue;
}
seach(xx, yy, x, y);
}
return 0;
}
void seach(const int &x, const int &y, const int &ex, const int &ey) {
queue<node> q;
q.push(node(x, y, 0));
vis[x][y] = true;
while (!q.empty()) {
node now = q.front();
q.pop();
if (pd(now.x, now.y, ex, ey)) {
printf("%d\n", now.t);
return;
}
for (int i = 0; i < 4; ++i) {
int nx = now.x + walk[i][0];
int ny = now.y + walk[i][1];
if (map[nx][ny] && !vis[nx][ny]) {
vis[nx][ny] = true;
q.push(node(nx, ny, now.t + 1));
}
}
}
printf("Poor Harry\n");
}
bool pd(const int &x, const int &y, const int &ex, const int &ey) {
for (int i = 0; i < 8; ++i) {
int nx = x, ny = y;
while (map[nx][ny]) {
if (nx == ex && ny == ey) {
return true;
}
nx += walk[i][0], ny += walk[i][1];
}
}
return false;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...