这个问题的核心解法是记忆化搜索 (DFS 缓存)。关键难点在于理解“永久卷轴”的等效处理否则直接模拟会超时。 核心思路与状态定义我们可以定义一个DFS函数 dfs(x, y, t, tmp, perm) 来搜索所有可能路径· (x, y)当前位置。· t当前时刻。· tmp布尔值表示临时卷轴是否已使用。· perm布尔值表示永久卷轴是否已使用。关于“永久卷轴”的等效处理永久消除一个陷阱等价于在那个位置原地等待一段时间。因此当我们在陷阱格子 (nx, ny) 上使用永久卷轴时不需要记录坐标只需尝试在 (nx, ny) 上停留不同的时长从下一时刻到最终时刻。 Python3 代码实现pythonfrom functools import lru_cachefrom typing import Listclass Solution:def escapeMaze(self, maze: List[List[str]]) - bool:max_t, n, m len(maze), len(maze[0]), len(maze[0][0])# 移动方向下、右、上、左、原地等待[reference:12]dirs [(1, 0), (0, 1), (-1, 0), (0, -1), (0, 0)]lru_cache(None)def dfs(x: int, y: int, t: int, tmp: bool, perm: bool) - bool:# 1. 到达终点if x n - 1 and y m - 1:return True# 2. 剪枝时间耗尽 或 剩余时间不足以走完最短路径[reference:13][reference:14]if t 1 max_t:return Falseif (n - 1 - x) (m - 1 - y) max_t - t - 1:return False# 3. 遍历所有可能的动作for dx, dy in dirs:nx, ny x dx, y dyif not (0 nx n and 0 ny m):continuenext_is_wall (maze[t 1][nx][ny] #)# --- 情况A下一格是空地 ---if not next_is_wall:if dfs(nx, ny, t 1, tmp, perm):return True# --- 情况B下一格是陷阱需要使用卷轴 ---else:# 4. 使用临时卷轴[reference:15]if not tmp:if dfs(nx, ny, t 1, True, perm):return True# 5. 使用永久卷轴[reference:16][reference:17]if not perm:# 在陷阱格 (nx, ny) 停留任意时长 (从 t1 到 max_t-1)for next_t in range(t 1, max_t):if dfs(nx, ny, next_t, tmp, True):return Truereturn False# 从起点(0,0)时刻0两个卷轴都未使用开始搜索return dfs(0, 0, 0, False, False) 复杂度分析· 时间复杂度$O(T \times N \times M \times 2 \times 2 \times T) O(T^2 \times N \times M)$。其中 $T$ 是总时刻数$N$ 和 $M$ 是迷宫尺寸。实际运行中剪枝会大幅优化。· 空间复杂度$O(T \times N \times M \times 2 \times 2) O(T \times N \times M)$用于存储记忆化搜索的缓存。核心就是通过DFS记忆化搜索并把“永久卷轴”等效为“原地等待”来简化状态。