题目重点：从路径显示与重复遍历修复开始，解释单向地形、钥匙状态、前驱重建和最短路径的正确性。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 示例采用矩形四邻网格、每步成本一；#墙、.空地、a–z永久可复用钥匙、A–Z对应锁。起终点用坐标传入，避免显示标记e/E与钥匙锁冲突。
- 箭头训练规则为必须沿箭头方向进入和离开；不自动跨墙、不自动滑行。禁止左右移动的地形、能穿墙的传送带属于不同变体，必须重新给出转移函数，不能套用此规则。
- 返回任意一条最短可行坐标路径；无路返回None。只在显示层将路径空地变*，保留特殊地形并显示入口/出口；未提供的工程类名和接口不补造。
- 普通0通路/1墙变体用solve_binary_maze，明确4邻接、返回任意最短坐标path，属于无钥匙无门的子集。允许8邻接的是独立训练合同，不从题目名字猜方向。
解题路线
- 先最小化失败用例：打印器核对path是否含入口出口，避免先覆盖再判断类型；BFS在入队时标记访问，每个状态只排队一次，不能等出队再允许无限重复入队。
- 访问状态为(row,col,keyMask)。同一个位置携带不同钥匙可以拥有不同后续路径。移动前检查边界、墙、当前格出方向、目标格入方向和锁权限；进入钥匙格后再更新位掩码。
- 每条合法转移成本一，BFS第一次取出目标即最短。parent保存完整前驱状态，终点沿链回溯再反转；每个队列元素只保存状态，避免复制整条路径。
- 改动前先读Maze、Cell、Printer、Solver的实际调用关系，再让AI处理明确的局部修改；用diff检查visited键、方向和标记，逐阶段回跑测试。AI输出不能取代状态不变量和用例解释。
- solve_binary_maze只做0→地板、1→墙的入口适配，复用同一BFS和前驱；无钥匙时mask始终0，因此退化到坐标visited。普通迷宫无需缓存每条完整候选路径。
手动走一遍
网格["..A.",".##.","a..."]，起点(0,0)、终点(0,3)。先向下取得a，再回到上排穿过A，共7步；仅以坐标去重会在回到起点时误剪枝。显示层["...."]的一条直线路径为e**E，含箭头的路径e>E保留箭头。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
DIRECTIONS = ((-1, 0), (0, 1), (1, 0), (0, -1))
ARROWS = {'^': 0, '>': 1, '↓': 2, '<': 3}
def solve_maze(board, start, goal):
"""Training contract: # wall, . floor, lowercase key, uppercase lock.
Down arrow is ↓, leaving the letter v available as a key.
Arrows require entering and leaving in their indicated movement direction.
Keys persist, may be reused, and do not remove corresponding locks.
Board uses coordinates for endpoints, avoiding E/e marker-key ambiguity.
Returns a shortest coordinate path or None. Input is not modified.
"""
if not board or not board[0]:
raise ValueError('nonempty rectangular board required')
h, w = len(board), len(board[0])
if any(len(row) != w for row in board):
raise ValueError('ragged board')
for p in (start, goal):
if len(p) != 2 or not (0 <= p[0] < h and 0 <= p[1] < w):
raise ValueError('endpoint outside board')
allowed = set('#.^>↓<abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ')
if any(c not in allowed for row in board for c in row):
raise ValueError('unknown terrain')
if board[start[0]][start[1]] == '#' or board[goal[0]][goal[1]] == '#':
return None
first_cell = board[start[0]][start[1]]
if first_cell.isupper(): # Initially no keys: a locked start is inaccessible.
return None
initial_keys = 1 << (ord(first_cell) - ord('a')) if first_cell.islower() else 0
first = (*start, initial_keys)
parent = {first: None}
queue = deque([first])
while queue:
current = queue.popleft()
r, c, keys = current
if (r, c) == goal:
path = []
while current is not None:
path.append(current[:2])
current = parent[current]
return path[::-1]
cell = board[r][c]
for direction, (dr, dc) in enumerate(DIRECTIONS):
if cell in ARROWS and ARROWS[cell] != direction:
continue
nr, nc = r + dr, c + dc
if not (0 <= nr < h and 0 <= nc < w):
continue
target = board[nr][nc]
if target == '#' or (target in ARROWS and ARROWS[target] != direction):
continue
if target.isupper() and not (keys & (1 << (ord(target.lower()) - ord('a')))):
continue
next_keys = keys | (1 << (ord(target) - ord('a'))) if target.islower() else keys
state = (nr, nc, next_keys)
if state not in parent:
parent[state] = (r, c, keys)
queue.append(state)
return None
def render_path(board, path, start_marker='e', goal_marker='E'):
"""Separate display contract; preserve non-floor tiles and endpoint markers."""
result = [list(row) for row in board]
for r, c in path or ():
if result[r][c] == '.':
result[r][c] = '*'
# Marker letters are a display option, not solver keys/locks.
if path:
r, c = path[0]; result[r][c] = start_marker
r, c = path[-1]; result[r][c] = goal_marker
return [''.join(row) for row in result]
def solve_binary_maze(grid,start,goal):
"""Plain 0/1 four-neighbor variant, rectangular; no keys or directed terrain."""
if not grid or not grid[0]:return None
width=len(grid[0])
if any(len(row)!=width or any(value not in (0,1) for value in row) for row in grid):raise ValueError('binary rectangle')
board=[''.join('#' if value else '.' for value in row) for row in grid]
return solve_maze(board,start,goal)
复杂度
有V=H×W格、K种实际钥匙，状态至多V×2^K，四邻转移下时间和parent/visited空间均O(V2^K)，路径重建O(L)。无钥匙退化O(V)。当前实现按字母位编码，最坏K=26；不宣称任意大型钥匙迷宫都高效。
易错点与追问
容易失分的边界
- 把visited写成坐标会遗漏拿钥匙后的新状态；以整条路径为状态则膨胀，必须只保存足以决定未来的状态。
- BFS解决单位步长，不适用于不同地形成本；改为0–1 BFS或Dijkstra。自动传送还要核对落点、环与代价。
- 入口出口显示字母不能直接当普通key/lock；示例将两层分开。遇到墙后的单向格不能凭方向允许穿墙。
- 向下箭头代码用↓，字母v仍可作钥匙；用v兼作箭头和钥匙会错误赋钥匙状态。
继续深挖
- 同坐标的钥匙集合A包含B且到达距离不大于B，可做支配剪枝；实现要保存距离和集合，不能简单只保留最新mask。
- 若只通过机器人move/turn接口探索未知地图，如何恢复位置与朝向？该题是实体探索，不等于直接访问完整网格的BFS。
- 大型工程中如何确认错误是printer、状态读取还是solver？先复现最小失败测试，限制修复范围，再做端到端回归。
