var dir4 = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func escapeMaze(g [][]string) bool {
k, n, m := len(g), len(g[0]), len(g[0][0])
vis := make([][][][6]bool, k)
for i := range vis {
vis[i] = make([][][6]bool, n)
for j := range vis[i] {
vis[i][j] = make([][6]bool, m)
}
}
// s 的最低位：是否使用了临时消除术
// s 的其余位：0-未使用永久消除术，1-当前正位于永久消除的位置，2-已使用永久消除术
var f func(t, x, y, s int) bool
f = func(t, x, y, s int) bool {
if x < 0 || x >= n || y < 0 || y >= m || t+n-1-x+m-1-y >= k || vis[t][x][y][s] {
return false
}
if x == n-1 && y == m-1 {
return true
}
vis[t][x][y][s] = true
if s>>1 == 1 {
for _, d := range dir4 {
if f(t+1, x+d.x, y+d.y, s^6) { // 跳出永久消除的位置
return true
}
}
return f(t+1, x, y, s)
}
if s>>1 == 0 && g[t][x][y] == '#' && f(t, x, y, s|2) { // 尝试使用永久消除术
return true
}
// 使用永久消除术已无法走到终点，遇到障碍只能使用临时消除术
if g[t][x][y] == '#' {
if s&1 == 1 {
return false
}
s |= 1
}
for _, d := range dir4 {
if f(t+1, x+d.x, y+d.y, s) {
return true
}
}
return f(t+1, x, y, s)
}
return f(0, 0, 0, 0)
}
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)
