企业官网建设流程全解析

这个问题的核心解法是记忆化搜索 (DFS + 缓存)。关键难点在于理解“永久卷轴”的等效处理，否则直接模拟会超时。

💡 核心思路与状态定义

我们可以定义一个DFS函数 dfs(x, y, t, tmp, perm) 来搜索所有可能路径：

· (x, y)：当前位置。
· t：当前时刻。
· tmp：布尔值，表示临时卷轴是否已使用。
· perm：布尔值，表示永久卷轴是否已使用。

关于“永久卷轴”的等效处理：永久消除一个陷阱，等价于在那个位置原地等待一段时间。因此，当我们在陷阱格子 (nx, ny) 上使用永久卷轴时，不需要记录坐标，只需尝试在 (nx, ny) 上停留不同的时长（从下一时刻到最终时刻）。

🚀 Python3 代码实现

```python
from functools import lru_cache
from typing import List

class 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 False
if (n - 1 - x) + (m - 1 - y) > max_t - t - 1:
return False

# 3. 遍历所有可能的动作
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if not (0 <= nx < n and 0 <= ny < m):
continue

next_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) 停留任意时长 (从 t+1 到 max_t-1)
for next_t in range(t + 1, max_t):
if dfs(nx, ny, next_t, tmp, True):
return True
return 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+记忆化搜索，并把“永久卷轴”等效为“原地等待”来简化状态。