题目重点：求起点到终点且必须经过指定坐标的最短行走路线，区分walk与不能重复格的简单路径。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练0/1矩形、4邻接、每步1，允许两段重访格；返回坐标path或None。必经点可与起点/终点相同。
- 如果禁止重复格，分别最短两段可能冲突，当前方法不适用；这一限制必须先问。
解题路线
- 任意通过waypoint的walk可拆start→waypoint和waypoint→goal，两段分别至少是各自最短距离。因此总下界d(start,w)+d(w,goal)。
- 各做一次BFS求最短段，拼first+second[1:]达到下界，所以全局最优。删第二段首点避免waypoint重复计一个格，但允许其他坐标在两段出现。
- 两次搜索各有自己的parent/visited，不能拿第一段visited阻止第二段经过已用格。任一段不可达则整体不可达，先检查三个坐标是否界内/可走。
- 方向门或key改变可达状态时，第一段到waypoint可能有多个keyMask，不能只取坐标最短段直接接第二段；需在完整状态图处理“是否已过w”。
手动走一遍
一行0格坐标0..3，start0、w3、goal1，最短walk为0,1,2,3,2,1，允许重访2/1。如果要求简单路径则无解，这说明两次BFS的合同必要。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def shortest_via(grid,start,waypoint,goal):
"""0 open/1 blocked, four neighbors, revisits allowed across the two legs."""
if not grid or not grid[0]:return None
rows,cols=len(grid),len(grid[0])
if any(len(row)!=cols or any(v not in (0,1) for v in row) for row in grid):raise ValueError('rectangular binary grid')
for r,c in (start,waypoint,goal):
if not 0<=r<rows or not 0<=c<cols:raise ValueError('coordinate outside grid')
if grid[r][c]:return None
def route(source,destination):
queue=deque([source]);parent={source:None}
while queue:
current=queue.popleft()
if current==destination:
result=[]
while current is not None:result.append(current);current=parent[current]
return result[::-1]
r,c=current
for dr,dc in ((-1,0),(1,0),(0,-1),(0,1)):
rr,cc=r+dr,c+dc;p=(rr,cc)
if 0<=rr<rows and 0<=cc<cols and grid[rr][cc]==0 and p not in parent:
parent[p]=(r,c);queue.append(p)
return None
first=route(start,waypoint)
if first is None:return None
second=route(waypoint,goal)
return first+second[1:] if second is not None else None
复杂度
O(RC)两次BFS仍同阶，前驱/队列O(RC)、输出O(L1+L2)。不用枚举所有可能start→goal路径再过滤必经点。
易错点与追问
容易失分的边界
- 复用第一段visited限制第二段会错误判无解。
- 忽略简单路径限制，输出重复格却声称满足题面。
继续深挖
- 多个必须依次经过的点可分段累加；顺序任意时为何出现组合优化？
- 若路径必须经过w恰好一次，第二段重复w需要禁止，合同与证明怎么调整？
