题目描述

某解密游戏中，有一个 n*m 的迷宫，迷宫地形会随时间变化而改变，迷宫出口一直位于 (n-1,m-1) 位置。迷宫变化规律记录于 maze 中，maze[i] 表示 i 时刻迷宫的地形状态，"." 表示可通行空地，"#" 表示陷阱。

地形图初始状态记作 maze[0]，此时小力位于起点 (0,0)。此后每一时刻可选择往上、下、左、右其一方向走一步，或者停留在原地。

小力背包有以下两个魔法卷轴（卷轴使用一次后消失）：

• 临时消除术：将指定位置在下一个时刻变为空地；
• 永久消除术：将指定位置永久变为空地。

请判断在迷宫变化结束前（含最后时刻），小力能否在不经过任意陷阱的情况下到达迷宫出口呢？

注意：输入数据保证起点和终点在所有时刻均为空地。

样例

输入：
maze = [
    [".#.","#.."],
    ["...",".#."],
    [".##",".#."],
    ["..#",".#."]
]

输出：true

解释：

输入：
maze = [
    [".#.","..."],
    ["...","..."]
]

输出：false

解释：由于时间不够，小力无法到达终点逃出迷宫。

输入：
maze = [
    ["...","...","..."],
    [".##","###","##."],
    [".##","###","##."],
    [".##","###","##."],
    [".##","###","##."],
    [".##","###","##."],
    [".##","###","##."]
]

输出：false

解释：由于道路不通，小力无法到达终点逃出迷宫。

限制

• 1 <= maze.length <= 100
• 1 <= maze[i].length, maze[i][j].length <= 50
• maze[i][j] 仅包含 "."、"#"

算法

(宽度优先搜索) $O(T^2nm)$

1. 设状态 $(t, x, y, temp, perm)$ 表示在 $t$ 时刻，临时消除使用情况为 $temp$，永久消除使用情况为 $perm$ 时，坐标 $(x, y)$ 能否到达。
2. 初始时，队列中插入状态 $(0, 0, 0, 0, 0)$。转移时，枚举 5 个方向。
3. 如果目标坐标为空地，且判断目标状态没有到达过，则目标状态进队。
4. 如果目标坐标为陷阱
   • 如果没有使用过临时消除，则可以使用临时消除，判断目标状是否到达过，然后进队。
   • 如果没有使用过永久消除，则可以使用永久消除，从下一时刻开始，目标坐标 都可以尝试进队。
5. 如果队列中出现了终点坐标，则返回 true。

时间复杂度

• 每个状态最多进队一次，出队一次。
• 每次转移最坏情况需要 $O(T)$ 的时间。
• 故总时间复杂度为 $O(T^2nm)$。由于并不是每次转移都会到最坏情况，故常数很小。

空间复杂度

• 需要 $O(Tnm)$ 的空间存储队列等数据结构。

C++ 代码

#define T 100
#define N 50

struct State {
    int t, x, y, temp, perm;
    State(int t, int x, int y, int temp, int perm) {
        this->t = t;
        this->x = x;
        this->y = y;
        this->temp = temp;
        this->perm = perm;
    }
};

class Solution {
private:
    bool seen[T][N][N][2][2];

public:
    bool escapeMaze(vector<vector<string>>& maze) {
        const int ti = maze.size();
        const int n = maze[0].size();
        const int m = maze[0][0].size();

        const int dx[5] = {0, 0, 1, 0, -1};
        const int dy[5] = {0, 1, 0, -1, 0};

        memset(seen, false, sizeof(seen));
        seen[0][0][0][0][0] = true;

        queue<State> q;
        q.push(State(0, 0, 0, 0, 0));

        while (!q.empty()) {
            State u = q.front();
            q.pop();
            if (u.x == n - 1 && u.y == m - 1)
                return true;

            for (int i = 0; i < 5; i++) {
                int t = u.t + 1;
                if (t >= ti)
                    continue;

                int x = u.x + dx[i], y = u.y + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m)
                    continue;

                if (maze[t][x][y] == '.') {
                    if (!seen[t][x][y][u.temp][u.perm]) {
                        seen[t][x][y][u.temp][u.perm] = true;
                        q.push(State(t, x, y, u.temp, u.perm));
                    }
                } else {
                    if (u.temp == 0) {
                        if (!seen[t][x][y][1][u.perm]) {
                            seen[t][x][y][1][u.perm] = true;
                            q.push(State(t, x, y, 1, u.perm));
                        }
                    }

                    if (u.perm == 0) {
                        while (t < ti) {
                            if (!seen[t][x][y][u.temp][1]) {
                                seen[t][x][y][u.temp][1] = true;
                                q.push(State(t, x, y, u.temp, 1));
                            }
                            t++;
                        }
                    }
                }
            }
        }

        return false;
    }
};