变换的迷宫

难度: Hard

某解密游戏中，有一个 N\*M 的迷宫，迷宫地形会随时间变化而改变，迷宫出口一直位于 `(n-1,m-1)` 位置。迷宫变化规律记录于 `maze` 中，`maze[i]` 表示 `i` 时刻迷宫的地形状态，`"."` 表示可通行空地，`"#"` 表示陷阱。地形图初始状态记作 `maze[0]`，此时小力位于起点 `(0,0)`。此后每一时刻可选择往上、下、左、右其一方向走一步，或者停留在原地。小力背包有以下两个魔法卷轴（卷轴使用一次后消失）： + 临时消除术：将指定位置在下一个时刻变为空地； + 永久消除术：将指定位置永久变为空地。请判断在迷宫变化结束前（含最后时刻），小力能否在不经过任意陷阱的情况下到达迷宫出口呢？ **注意：输入数据保证起点和终点在所有时刻均为空地。** **示例 1：** >输入：`maze = [[".#.","#.."],["...",".#."],[".##",".#."],["..#",".#."]]` > >输出：`true` > >解释： ![maze.gif](https://pic.leetcode-cn.com/1615892239-SCIjyf-maze.gif) **示例 2：** >输入：`maze = [[".#.","..."],["...","..."]]` > >输出：`false` > >解释：由于时间不够，小力无法到达终点逃出迷宫。 **示例 3：** >输入：`maze = [["...","...","..."],[".##","###","##."],[".##","###","##."],[".##","###","##."],[".##","###","##."],[".##","###","##."],[".##","###","##."]]` > >输出：`false` > >解释：由于道路不通，小力无法到达终点逃出迷宫。 **提示：** - `1 <= maze.length <= 100` - `1 <= maze[i].length, maze[i][j].length <= 50` - `maze[i][j]` 仅包含 `"."`、`"#"`

Submission

运行时间: 510 ms

内存: 43.6 MB

class Solution:
    def escapeMaze(self, maze: List[List[str]]) -> bool:
        max_dep, n, m = len(maze), len(maze[0]), len(maze[0][0])
        # 下一点移动方式
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]
        # 记忆化搜索（为python缓存机制）
        @lru_cache(None)
        def dfs(x, y, dep, magic_a, magic_b):
            # print(x, y, dep, magic_a, magic_b)
            if x == n - 1 and y == m - 1:
                return True
            if dep + 1 == max_dep:
                return False
            # 剪枝
            if n - 1 - x + m - 1 - y > max_dep - dep - 1:
                return False
            for i, j in dirs:
                xx, yy = x + i, y + j
                if xx < 0 or xx == n or yy < 0 or yy == m:
                    continue
                # 下一点为平地
                if maze[dep + 1][xx][yy] == '.':
                    if dfs(xx, yy, dep + 1, magic_a, magic_b):
                        return True
                # 下一点需要使用卷轴
                else:
                    if not magic_a:
                        # 临时卷轴
                        if dfs(xx, yy, dep + 1, True, magic_b):
                            return True
                    if not magic_b:
                        # 用永久卷轴保持不动
                        for next_dep in range(dep + 1, max_dep):
                            if dfs(xx, yy, next_dep, magic_a, True):
                                return True
            return False
        return dfs(0, 0, 0, False, False)

Explain

题解采用了深度优先搜索（DFS）结合记忆化的方法来解决问题。首先，函数通过递归尝试所有可能的路径来探索迷宫。每个递归调用尝试从当前位置（x, y）在当前时间（dep）向四个方向以及原地（共五种可能）移动，并考虑是否使用两种魔法卷轴。记忆化通过Python的装饰器lru_cache实现，这可以避免重复计算已经探索过的状态。剪枝操作包括检查是否可能在剩余的时间内到达终点，即通过简单的距离和时间比较来快速剪除不可能的路径。如果能在迷宫变化结束前到达终点，则返回true，否则在所有可能都尝试后返回false。

时间复杂度: O(n * m * max_dep)

空间复杂度: O(n * m * max_dep)

class Solution:
    def escapeMaze(self, maze: List[List[str]]) -> bool:
        max_dep, n, m = len(maze), len(maze[0]), len(maze[0][0])
        # 下一点移动方式
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]
        # 记忆化搜索（为python缓存机制）
        @lru_cache(None)
        def dfs(x, y, dep, magic_a, magic_b):
            if x == n - 1 and y == m - 1:
                return True
            if dep + 1 == max_dep:
                return False
            # 剪枝
            if n - 1 - x + m - 1 - y > max_dep - dep - 1:
                return False
            for i, j in dirs:
                xx, yy = x + i, y + j
                if xx < 0 or xx == n or yy < 0 or yy == m:
                    continue
                if maze[dep + 1][xx][yy] == '.':
                    if dfs(xx, yy, dep + 1, magic_a, magic_b):
                        return True
                else:
                    if not magic_a:
                        if dfs(xx, yy, dep + 1, True, magic_b):
                            return True
                    if not magic_b:
                        for next_dep in range(dep + 1, max_dep):
                            if dfs(xx, yy, next_dep, magic_a, True):
                                return True
            return False
        return dfs(0, 0, 0, False, False)

Explore

在解决路径搜索问题时，DFS和BFS各有优势。DFS的优点在于其空间复杂度通常比BFS低，因为DFS只需存储单条路径上的节点，而BFS需要存储整个层级的节点。对于变换的迷宫这种需要探索多种状态（位置，时间，和魔法使用情况）的问题，DFS能更有效地探索深层状态，尤其当配合剪枝和记忆化时，能快速排除无效路径。此外，DFS在找到一条有效路径时可以立即终止整个搜索，这对于此类问题是一个明显的优势。

在Python中使用lru_cache装饰器时，参数None意味着缓存的大小（即可以存储多少个不同的调用结果）是无限的。这在递归深度优先搜索中非常有用，因为可能会有大量的不同状态需要缓存，从而避免重复计算。无限的缓存尺寸确保了所有可能的状态都被记忆，这对于提高算法的效率是非常有帮助的，特别是在有大量可能状态的问题中。

此剪枝条件基于最简单的距离和时间的估算。`n - 1 - x + m - 1 - y`计算的是从当前位置(x, y)到目标位置(n-1, m-1)的曼哈顿距离，即最少需要的步数。`max_dep - dep - 1`计算的是从当前时间点(dep)到迷宫变化停止的时间(max_dep)之前，还可以进行的最大移动次数。如果所需的最少步数超过了剩余可移动的次数，那么无论如何都不可能在迷宫变化完成前到达终点，因此这条路径可以被剪枝，即直接判断为不可能成功的路径，从而节省搜索时间。