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;
}