Bailian4129 变换的迷宫【BFS】

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++语言程序如下：

1/* Bailian4129 变换的迷宫 */
2
3#include <bits/stdc++.h>
4
5using namespace std;
6
7const int N = 100, K = 10;
8char maze[N][N + 1];
9bool vis[N][N][K];
10struct Node {
11    int row, col, time;
12    Node(int r, int c, int t):row(r), col(c),time(t){}
13};
14int dr[] = {-1, 1, 0, 0};
15int dc[] = {0, 0, -1, 1};
16const int DL = sizeof(dr) / sizeof(int);
17
18int main()
19{
20    int t, r, c, k;
21    scanf("%d", &t);
22    while(t--) {
23        queue<Node> q;
24
25        scanf("%d%d%d", &r, &c, &k);
26        for(int i = 0; i < r; i++)
27            scanf("%s", maze[i]);
28
29        memset(vis, false, sizeof(vis));
30        int tr, tc, cnt = 0;
31        for(int i = 0; i < r; i++)
32            for(int j = 0; j < c; j++)
33                if(maze[i][j] == 'S') {
34                    q.push(Node(i, j, 0));
35                    vis[i][j][0] = true;
36                    if(++cnt == 2) break;
37                } else if(maze[i][j] == 'E') {
38                   tr = i;
39                   tc = j;
40                   if(++cnt == 2) break;
41                }
42
43        while(!q.empty()) {
44            Node t = q.front();
45            if(t.row == tr && t.col == tc) break;
46            q.pop();
47            for(int i = 0; i < DL; i++) {
48                int nrow = t.row + dr[i];
49                int ncol = t.col + dc[i];
50                if(nrow < 0 || nrow >= r || ncol < 0 || ncol >= c)
51                    continue;
52                if(vis[nrow][ncol][(t.time + 1) % k])
53                    continue;
54                if((t.time + 1) % k && maze[nrow][ncol] == '#') // 时间是K 的倍数时，迷宫中的石头就会消失
55                    continue;
56                vis[nrow][ncol][(t.time + 1) % k] = true;
57                q.push(Node(nrow, ncol, t.time + 1));
58            }
59        }
60
61        if(q.empty())
62            printf("Oop!\n");
63        else
64            printf("%d\n", q.front().time);
65    }
66
67    return 0;
68}