@[DreamCHN](/user/1010657) 没开动态数组,但是时间复杂度是 $O(n^3)$,需要优化。
这是目前 TLE 但保证正确性的代码:
```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;
}
};
vector<bool> map[16385];
vector<bool> vis[16385];
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) {
vis[i].resize(m+5),map[i].resize(m+5);
for (int j = 1; j <= m; ++j) {
char temp;
cin >> temp;
map[i][j] = ((temp == 'X') ? false : true),vis[i][j] = 0;
}
}
int x, y, xx, yy;
while (1) {
scanf("%d%d%d%d", &x, &y, &xx, &yy);
for(int i = 1;i<=n;i++)
for(int j = 1;j<=m;j++)
vis[i][j] = 0;
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(nx<1||nx>n||ny<1||ny>m) continue;
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 (nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[nx][ny]) {
if (nx == ex && ny == ey) {
return true;
}
nx += walk[i][0], ny += walk[i][1];
}
}
return false;
}
```
by pyy1 @ 2023-11-13 21:59:52
@[DreamCHN](/user/1010657) 还有就是要注意边界的判定。
by pyy1 @ 2023-11-13 22:00:54
@[pyy1](/user/581316) 谢谢
by DreamCHN @ 2023-11-14 18:42:30