题意比较啰嗦。
就是搜索加上一些特殊的条件，比如可以在原地不动，也就是在原地呆一秒，如果有监控也可以花3秒的时间走过去。
这种类型的题目还是比较常见的。以下代码b[i][j][x]表示格子i行j列在x时刻有监控照的到。因为只有4个方向，所以只需要时间对4取模就行。具体细节见代码。
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int maxn = 550; const int dx[5] = {0, 0, 1, -1, 0}, dy[5] = {1, -1, 0, 0, 0}; char mp[maxn][maxn]; int b[maxn][maxn][4]; int T, n, kase; bool vis[maxn][maxn][4]; struct Node { int x, y, step; bool operator < (const Node &b) const { return step > b.step; } }; Node tar; int bfs(int x, int y) { memset(vis, false, sizeof(vis)); priority_queue<Node> Q; Node cur, nex; cur.x = x; cur.y = y; cur.step = 0; vis[x][y][0] = true; Q.push(cur); while (!Q.empty()) { cur = Q.top(); Q.pop(); if (tar.x == cur.x && tar.y == cur.y) return cur.step; for (int i = 0; i < 5; i++)//最后一个状态是可以呆在原地不动 { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (mp[nx][ny] == '#') continue; nex = cur; if (b[nx][ny][cur.step % 4] || b[cur.x][cur.y][cur.step % 4])//如果下一个位置有监控或者当前这个位置监控的到 { if (nx == cur.x && ny == cur.y && !vis[nx][ny][(cur.step + 1) % 4])//如果当前这个位置监控的到, { nex.step++; vis[nx][ny][nex.step % 4] = true; Q.push(nex); } else if (!vis[nx][ny][(cur.step + 3) % 4])//如果下一个监控的到 { nex.x = nx; nex.y = ny; nex.step += 3; vis[nx][ny][nex.step % 4] = true; Q.push(nex); } } else if (!vis[nx][ny][(cur.step + 1) % 4])//否则直接走 { nex.x = nx; nex.y = ny; nex.step++; vis[nx][ny][nex.step % 4] = true; Q.push(nex); } } } return -1; } int main() { scanf("%d", &T); while (T--) { int x, y; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%s", mp[i]); memset(b, 0, sizeof(b)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (mp[i][j] == 'M') { x = i; y = j; } else if (mp[i][j] == 'N') { b[i][j][0] = b[i][j][1] = b[i][j][2] = b[i][j][3] = 1;//它本身这个位置不管任意时刻都被监控到 if (i - 1 >= 0) b[i - 1][j][0] = 1;//表示紧挨着它上面的那个在1秒的时候被监控到 if (j + 1 < n) b[i][j + 1][1] = 1;//紧挨着它右边的在第2秒的时候,意思就是下一秒 if (i + 1 < n) b[i + 1][j][2] = 1;//下两秒 if (j - 1 >= 0) b[i][j - 1][3] = 1;//下三秒在忘左边的位置被监控的到 } else if (mp[i][j] == 'E') { b[i][j][0] = b[i][j][1] = b[i][j][2] = b[i][j][3] = 1; if (i - 1 >= 0) b[i - 1][j][3] = 1; if (j + 1 < n) b[i][j + 1][0] = 1; if (i + 1 < n) b[i + 1][j][1] = 1; if (j - 1 >= 0) b[i][j - 1][2] = 1; } else if (mp[i][j] == 'S') { b[i][j][0] = b[i][j][1] = b[i][j][2] = b[i][j][3] = 1; if (i - 1 >= 0) b[i - 1][j][2] = 1; if (j + 1 < n) b[i][j + 1][3] = 1; if (i + 1 < n) b[i + 1][j][0] = 1; if (j - 1 >= 0) b[i][j - 1][1] = 1; } else if (mp[i][j] == 'W') { b[i][j][0] = b[i][j][1] = b[i][j][2] = b[i][j][3] = 1; if (i - 1 >= 0) b[i - 1][j][1] = 1; if (j + 1 < n) b[i][j + 1][2] = 1; if (i + 1 < n) b[i + 1][j][3] = 1; if (j - 1 >= 0) b[i][j - 1][0] = 1; } else if (mp[i][j] == 'T') { tar.x = i; tar.y = j; } } } printf("Case #%d: %d ", ++kase, bfs(x, y)); } return 0; }