题目重点：三问的目标不同，全部路径输出不能套BFS全局visited。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 0格可走、1格障碍，四邻接；起点为首行任一可走格，第一次进入底行即结束。矩阵矩形。
- 权重为非负格子进入费用，包含起点；所有路径不重复格子。若允许仅向下、费用仅边或必须指定起点须调整。
解题路线
- 可达单独用多源BFS，起点同时入队，O(RC)。代码的all_paths为教学生成器，用当前路径seen回溯，不能用永久visited压掉另一合法路径。
- weighted把所有首行起点以自身费用初始化Dijkstra，弹出首个底行节点即全局最优。非负费用保证settle正确，零费用环不需重复走。
- 路径数可能指数甚至更快增长，generator只减少同时输出存储，不减少枚举时间。生产接口要限制maxPaths/超时并标明截断，不能偷偷裁剪后称全部。
手动走一遍
1行网格每个可走格即一条长度1路径，最短费用取首行最低格权重。2×2全通网格到不同底格有多个简单路径，同节点可处于不同搜索分支。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from heapq import heappush,heappop
def neighbors(grid,r,c):
for x,y in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
if 0<=x<len(grid) and 0<=y<len(grid[0]) and grid[x][y]==0:yield x,y
def all_paths(grid):
if not grid or not grid[0]:return
def dfs(r,c,path,seen):
if r==len(grid)-1:yield tuple(path);return
for cell in neighbors(grid,r,c):
if cell not in seen:
seen.add(cell);path.append(cell)
yield from dfs(*cell,path,seen)
path.pop();seen.remove(cell)
for c in range(len(grid[0])):
if grid[0][c]==0:yield from dfs(0,c,[(0,c)],{(0,c)})
def shortest(grid,weights):
if not grid or not grid[0]:return None
if len(weights)!=len(grid) or any(len(row)!=len(grid[0]) for row in grid+weights):raise ValueError("shape")
if any(w<0 for row in weights for w in row):raise ValueError("nonnegative weights")
best={};heap=[]
for c in range(len(grid[0])):
if grid[0][c]==0:best[(0,c)]=weights[0][c];heappush(heap,(weights[0][c],0,c))
while heap:
cost,r,c=heappop(heap)
if best[(r,c)]!=cost:continue
if r==len(grid)-1:return cost
for x,y in neighbors(grid,r,c):
new=cost+weights[x][y]
if new<best.get((x,y),float('inf')):best[(x,y)]=new;heappush(heap,(new,x,y))
return None
复杂度
可达O(V+E)；全部路径O(探索路径前缀总量+输出字符量)，stack O(V)；Dijkstra网格O(VlogV)时间/O(V)空间。
易错点与追问
容易失分的边界
- 所有路径用全局visited会漏结果。
- 负权不能用Dijkstra，允许负环时最短路可能不存在。
继续深挖
- 仅允许向下/左右时可否改DAG DP，左右仍可能产生环吗？
- 要最短路径本身，如何存多源parent且区分起点？
