题目重点：顺箭头移动成本 0，改当前格箭头成本 1；用双端队列求左上到右下最少修改。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版矩形非空网格，每格方向编码 1右/2左/3下/4上；上下左右可走，顺当前箭头代价 0，逆向走等价于把当前格改向代价 1。
- 目标是找到一条路径上的最少改动，允许重复访问但非负权最短路可取无重复最优路径；题目未规定多次访问同格的全局改向一致性，此训练映射按经典模型。
解题路线
- 把每格作图节点，到四邻格建有向边。走本格箭头所指边权 0，其余边权 1。于是题目成为 0/1 边权最短路。
- 双端队列从起点出发：松弛出 0 权边放队首，1 权边放队尾；维护 dist[r][c]，过期条目跳过。首次确定的最低代价与 Dijkstra 等价，但不用堆。
- 普通无权 BFS 只按步数分层，可能选择更短但改动更多的路径；Dijkstra 可用 O(MN log MN)，0-1 BFS 利用边权限定做到 O(MN)。
- 若真实规则规定改变一个格后所有后续访问都永久采用新方向，需把改向状态计入图状态；不能直接沿用经典 0-1 BFS。
手动走一遍
2×2 网格右、下/右、右：从 (0,0) 顺右到 (0,1)，再顺下到 (1,1)，改向数 0；若第二格箭头向上，则这一步 cost 1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
MOVES = ((0, 1), (0, -1), (1, 0), (-1, 0)) # right, left, down, up
def minimum_changes(grid: list[list[int]]) -> int:
if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
raise ValueError("nonempty rectangular grid required")
rows, cols = len(grid), len(grid[0])
if any(direction not in (1, 2, 3, 4) for row in grid for direction in row):
raise ValueError("directions must be 1..4")
distance = [[float("inf")] * cols for _ in range(rows)]
distance[0][0] = 0
queue = deque([(0, 0, 0)])
while queue:
current, r, c = queue.popleft()
if current != distance[r][c]:
continue
for direction, (dr, dc) in enumerate(MOVES, 1):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
cost = 0 if grid[r][c] == direction else 1
if current + cost < distance[nr][nc]:
distance[nr][nc] = current + cost
if cost == 0:
queue.appendleft((current, nr, nc))
else:
queue.append((current + 1, nr, nc))
return int(distance[-1][-1])
复杂度
R×C 节点、每格≤4 条边，0-1 BFS O(RC) 时间和 O(RC) dist/队列空间；训练代码 12,000 组随机网格与独立堆式 Dijkstra 对照。
易错点与追问
容易失分的边界
- 用普通 BFS 最短步数当最少改向数。
- 改到目标邻居时误按目标格箭头计费，实际改当前格。
- 0 权边也放队尾，破坏非降距离顺序。
- 不检查网格矩形/方向合法。
- 把永久改向全局状态与按路径边收费两种契约混淆。
继续深挖
- 加入障碍如何处理？
- 若改方向成本不是 1 而是任意非负数？
- 若要返回具体路径和改动格子？
- 永久改向并允许环路时状态空间如何定义？
