4129:变换的迷宫 总时间限制: 1000ms 内存限制: 65536kB 描述 你现在身处一个R*C 的迷宫中，你的位置用"S" 表示，迷宫的出口用"E" 表示。
迷宫中有一些石头，用"#" 表示，还有一些可以随意走动的区域，用"." 表示。
初始时间为0 时，你站在地图中标记为"S" 的位置上。你每移动一步（向上下左右方向移动）会花费一个单位时间。你必须一直保持移动，不能停留在原地不走。
当前时间是K 的倍数时，迷宫中的石头就会消失，此时你可以走到这些位置上。在其余的时间里，你不能走到石头所在的位置。
求你从初始位置走到迷宫出口最少需要花费多少个单位时间。
如果无法走到出口，则输出"Oop!"。
输入 第一行是一个正整数 T，表示有 T 组数据。 每组数据的第一行包含三个用空格分开的正整数，分别为 R、C、K。 接下来的 R 行中，每行包含了 C 个字符，分别可能是 “S”、“E”、"#" 或 “.”。 其中，0 < T <= 20，0 < R, C <= 100，2 <= K <= 10。 输出 对于每组数据，如果能够走到迷宫的出口，则输出一个正整数，表示最少需要花费的单位时间，否则输出 “Oop!”。 样例输入 1 6 6 2 …S… …#… .#… …#… …#… …#E#. 样例输出 7
问题链接：Bailian4129 变换的迷宫 问题简述：（略） 问题分析：在迷宫中走动，时间点为k的倍数时，石头会消失（石头的地方也可以走）。对于每个坐标点，还需要考虑走到该点的时间除以k的余数，各种余数都走过了，才算走过了该坐标点。所以，判定一种状态是否出现过的vis[][][]，除了行列坐标，还要考虑时间点（余数）。由于是走一格算一步，所以使用普通队列来实现就可以了，不需要优先队列。 程序说明：（略） 参考链接：Bailian4116 拯救行动【优先搜索】 题记：求最优解问题，一般需要用BFS或优先搜索来解决。
AC的C++语言程序如下：
/* Bailian4129 变换的迷宫 */ #include <bits/stdc++.h> using namespace std; const int N = 100, K = 10; char maze[N][N + 1]; bool vis[N][N][K]; struct Node { int row, col, time; Node(int r, int c, int t):row(r), col(c),time(t){} }; int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; const int DL = sizeof(dr) / sizeof(int); int main() { int t, r, c, k; scanf("%d", &t); while(t--) { queue<Node> q; scanf("%d%d%d", &r, &c, &k); for(int i = 0; i < r; i++) scanf("%s", maze[i]); memset(vis, false, sizeof(vis)); int tr, tc, cnt = 0; for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(maze[i][j] == 'S') { q.push(Node(i, j, 0)); vis[i][j][0] = true; if(++cnt == 2) break; } else if(maze[i][j] == 'E') { tr = i; tc = j; if(++cnt == 2) break; } while(!q.empty()) { Node t = q.front(); if(t.row == tr && t.col == tc) break; q.pop(); for(int i = 0; i < DL; i++) { int nrow = t.row + dr[i]; int ncol = t.col + dc[i]; if(nrow < 0 || nrow >= r || ncol < 0 || ncol >= c) continue; if(vis[nrow][ncol][(t.time + 1) % k]) continue; if((t.time + 1) % k && maze[nrow][ncol] == '#') // 时间是K 的倍数时，迷宫中的石头就会消失 continue; vis[nrow][ncol][(t.time + 1) % k] = true; q.push(Node(nrow, ncol, t.time + 1)); } } if(q.empty()) printf("Oop!\n"); else printf("%d\n", q.front().time); } return 0; }