Rat in a Maze
一只老鼠从 n × n 的 maze 左上角单元格出发，其中 1 表示可通行的单元格，0 表示墙，它必须到达右下角单元格。每次移动一格，向下（D）、向左（L）、向右（R）或向上（U），并且只能进入可通行的单元格。路径不能重复经过同一个单元格，并且必须在出口结束。
按字母顺序返回所有移动路径组成的字符串；如果没有路径，则返回空数组。
函数
- mazeinteger-2d-array
- n × n 网格，其中 1 表示可通行单元格，0 表示墙
- 返回值string-array
- 按字母顺序，将从左上角到右下角的每条路径表示为移动字符串
约束条件
2 ≤ n ≤ 5maze[i][j]是0或1。- 每个测试迷宫最多有 2,000 条路径。没有障碍的 5 × 5 迷宫有 8,512 条路径，因此不会出现在测试中。
示例
- 输入
- maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
- 输出
- ["RDDRDR", "RDRDDR"]
- 解释
- 一开始只有右边的格子是开放的，从那里出发也只有下面的格子是开放的，所以两条路径都以
RD开始。RDDRDR排在前面，因为它的第三步D在R之前。
- 输入
- maze = [[1, 1, 1], [1, 0, 1], [1, 1, 0]]
- 输出
- []
- 解释
- 出口，也就是右下角的单元格，是一堵墙，所以没有路径能在那里结束，答案为空，尽管其他所有单元格都是畅通的。
进阶
允许进行全部四种移动后，你能不逐条列出路径，直接数出路径总数吗？在路径总数大到无法计算之前，n 最大能是多少？
提示
逐个打开提示，每个都会多透露一点。
路径是从起点单元格开始的一系列移动，所以要一次移动一步来构建路径。每个单元格最多有四种移动方式：哪些是允许的？
用递归函数向前移动，并在离开当前格子前将它标记为已使用，这样路径就无法再返回这里。函数调用返回后，取消标记：其他路径仍可能经过这个格子。
按字母顺序尝试移动：
D、L、R、U。两条路径首次出现差异的位置就是它们分开的移动，因此会先探索字母较小的分支，这样得到的路径已经排好序。
题解
你必须列出每条路径，不能重复，也不能遗漏。回溯可以做到这一点：每次移动一步来延长路径，阻止路径经过的单元格，并在退回时解除对每个单元格的阻止。按字母顺序尝试移动方向，就能让路径按顺序排列。
先按广度优先的方式扩展每条路径，然后排序
思路
维护一个部分路径队列，每条路径都包含所在单元格、已走过的单元格和移动记录。取出一条路径，将它的所有一步扩展路径放回队列，扩展到相邻的开放且未使用的单元格；如果到达出口，就保存这条路径。每条路径恰好会被找到一次。最多有 25 个单元格时，可以用一个整数存储已使用单元格集合：位 r * n + c 表示单元格 (r, c)。
队列会优先取出最短路径，但这并不代表路径已经排好序。在开放的 5 × 5 迷宫中，16 步的 DDDDRRRULLURRRDD 会排在 8 步的 DDDRDRRR 前面。因此，你要在最后排序，而队列会在内存中保存一整层部分路径。
算法
- 如果起点或出口是墙，返回一个空数组。
- 将起点加入队列：单元格
(0, 0)，已使用集合中包含第 0 位，没有移动。 - 取出下一个条目。如果它位于出口，就保存它的移动路径并继续。
- 否则，对于每个移动到迷宫内开放且未使用单元格的移动，都添加一个条目，其中包含该单元格、将该单元格对应的位加入已使用集合后的集合，以及追加了这次移动的路径。
- 队列为空时，对保存的路径排序并返回。
from collections import deque
def findPaths(maze):
n = len(maze)
if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
return []
moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
result = []
# Each entry is a path in progress: its cell, the cells it has used
# (bit r * n + c), and its moves so far.
queue = deque([(0, 0, 1, "")])
while queue:
r, c, used, path = queue.popleft()
if r == n - 1 and c == n - 1:
result.append(path)
continue
for letter, dr, dc in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
bit = 1 << (nr * n + nc)
if not used & bit:
queue.append((nr, nc, used | bit, path + letter))
result.sort() # shorter paths were found first, so sort by text
return result按字母顺序进行回溯
思路
递归函数位于一个单元格上。到达出口时，它会保存移动记录。否则，它会将该单元格设为 0，这样路径就无法返回，然后尝试移动到每个开放的单元格，并将该单元格设回 1，因为后续路径可能会经过这里。内存中保存的是当前路径，递归深度最多为 n²。
两条路径在首次出现不同移动之前共享相同的移动记录，而搜索会先完成字母较小的那个分支。路径也会在到达出口时停止，因此一条路径不会是另一条路径的开头。按 D、L、R、U 的顺序尝试移动后，保存的路径自然就是排序后的。
算法
- 如果起点或出口是墙，返回一个空数组。
- 编写
backtrack(r, c)。如果(r, c)是出口，保存当前路径并返回。 - 将
maze[r][c]设为 0。 - 按
D、L、R、U的顺序尝试每个移动。如果移动后到达迷宫内的开放单元格，就追加对应的字母，递归调用，然后移除该字母。 - 将
maze[r][c]设回 1。调用backtrack(0, 0)，并返回保存的路径。
def findPaths(maze):
n = len(maze)
result = []
if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
return result
# The moves in alphabetical order, so the paths come out sorted.
moves = (("D", 1, 0), ("L", 0, -1), ("R", 0, 1), ("U", -1, 0))
path = []
def backtrack(r, c):
if r == n - 1 and c == n - 1:
result.append("".join(path))
return
maze[r][c] = 0 # block the cell while this path uses it
for letter, dr, dc in moves:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
path.append(letter)
backtrack(nr, nc)
path.pop()
maze[r][c] = 1 # open it again for the other paths
backtrack(0, 0)
return result
易错点和边界情况
- 回退时忘记取消标记单元格。这个单元格会一直被阻挡，因此之后的分支都无法经过它。在一个开放的 3 × 3 迷宫中，这会导致返回
DDRR和DDRURD，即 12 条路径中的 2 条。 - 忘记起点或出口也可能是墙。像第二个示例那样，如果出口处有一堵墙，答案必须为空，而不是一条终点在墙旁边的路径。
- 尝试按向下、向上、向左、向右的顺序移动。路径集合是对的，但顺序不对；
D、L、R、U才是按字母顺序排列的。
常见问题3
老鼠走迷宫的时间复杂度是多少？
首次移动后，路径在每个格子处最多有三种选择，并且最多经过 n² 个格子，因此共有 O(3^(n²)) 条部分路径，每条路径写出需要 O(n²) 的时间。墙和已使用的格子会大幅减少这个数量。
为什么回溯时必须移除已访问标记？
这个标记必须表示“当前路径上的单元格”，而不是“之前访问过的单元格”。两条不同的路径可能经过同一个单元格。如果搜索回退后单元格仍保留标记，那么之后所有经过该单元格的路径都会被遗漏。
如果老鼠只能向右和向下移动呢？
这样就没有路径会再次经过同一个单元格，因此你不需要标记已访问的单元格，而且每条路径都恰好有 2n-2 步。计算路径数量可以使用动态规划：到达某个单元格的方法数，等于到达它上方开放单元格的方法数加上到达它左侧开放单元格的方法数。
def findPaths(maze):
# 在这里编写代码测试 #1
测试 #2
参数
maze = [[1, 1, 0, 0], [0, 1, 1, 0], [1, 1, 1, 0], [1, 0, 1, 1]]
预期输出
["RDDRDR", "RDRDDR"]