题目重点：按同一模式连通的网格求每种方式最短步数，时间优先、费用破平局，并讨论换乘/转弯成本变体。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 矩形网格只有一个 S 和 D；普通格子以 1..K 标模式，X 不可过，四方向移动；从 S 选择一种模式后仅走该模式格子，直到 D。
- 称总时间/费用由路径经过格子累计，但 S/D 无模式；训练代码按每次移动算一个 block，包含最后进入 D 的一步，S 本身不收费。若面试官按普通模式格子计步，候选模式间通常仍可比较，但金额/时长示例要一致。
- 同一模式每步时间、费用都是常量且时间正；若同时间同费用，训练版按 modes 数组顺序稳定选。题目未明确最后平局规则。
解题路线
- 对每种模式分别 BFS 能求该模式最少步数，但 K 个模式共 O(KRC)。每个普通格子的数字唯一，不能在不同模式共享；从 S 把相邻数字格子入同一个队列，BFS 只沿相同数字扩展，相当于同时跑各模式 BFS，每格至多入队一次。
- 遇到 D 时记录进入该 D 的模式与步数；BFS 的首次到达是该模式最短步数，多个模式可分别记录。某模式用步数 d 时，时间 d·times[i]，费用 d·costs[i]；按 (时间,费用,稳定模式序号) 取最小。
- 若追问转弯有成本，状态需加入上一步方向，边权可能不同，通常用 Dijkstra；若允许换乘，状态要保留当前模式且换乘边/代价明确，原 O(RC) 推理不再直接适用。
- 网格无路径返回空串；S 与 D 直接相邻但没模式的情况原题未定义，训练版不认为有有效模式。
手动走一遍
S 左侧连接模式 1 的 4 步路径、右侧模式 2 的 3 步路径；若 times=[2,3]，总时间 8 与 9，选模式 1，即使模式 2 路更短。若模式 1 为 3 步，两者同为 6/9 的比较还需看 costs；不能只选步数最少。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Training contract for the visible Databricks Optimal Commute grid.
Each S->...->D movement costs one block's time/cost in the chosen mode.
S and D are endpoints with no own mode; this resolves an ambiguity in one
post's 'cells visited' phrasing. Each ordinary cell has exactly one mode.
"""
from collections import deque
def optimal_commute(grid: list[str], modes: list[str], times: list[int], costs: list[int]) -> str:
if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
raise ValueError("grid must be a nonempty rectangle")
if len(modes) != len(times) or len(modes) != len(costs):
raise ValueError("mode arrays must have equal length")
if any(t <= 0 for t in times) or any(c < 0 for c in costs):
raise ValueError("time must be positive and cost nonnegative")
rows, cols = len(grid), len(grid[0])
starts = [(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "S"]
ends = [(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "D"]
if len(starts) != 1 or len(ends) != 1 or len(modes) > 9:
raise ValueError("one S, one D, and at most nine digit modes required")
legal = set("SDX") | {str(i) for i in range(1, len(modes) + 1)}
if any(ch not in legal for row in grid for ch in row):
raise ValueError("unknown grid symbol")
sr, sc = starts[0]
queue = deque([(sr, sc, 0)])
seen = {(sr, sc)}
best_steps: dict[int, int] = {}
while queue:
r, c, steps = queue.popleft()
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if not (0 <= nr < rows and 0 <= nc < cols):
continue
current, nxt = grid[r][c], grid[nr][nc]
if nxt == "X" or nxt == "S":
continue
if current == "S":
if not nxt.isdigit():
continue
elif nxt != "D" and nxt != current:
continue
mode = int(nxt if current == "S" else current) - 1
if nxt == "D":
best_steps[mode] = min(best_steps.get(mode, rows * cols + 1), steps + 1)
elif (nr, nc) not in seen:
seen.add((nr, nc))
queue.append((nr, nc, steps + 1))
if not best_steps:
return ""
winner = min(best_steps, key=lambda i: (best_steps[i] * times[i], best_steps[i] * costs[i], i))
return modes[winner]
复杂度
R×C 网格，每格入队至多一次且每次检查四邻，O(RC) 时间、O(RC+K) 空间；逐模式 BFS 是 O(KRC) 时间。若转弯或换乘使状态扩张到方向/模式，复杂度要按新状态图重算。
易错点与追问
容易失分的边界
- 把多模式格子混走，却未计算换乘。
- 只比较 BFS 步数，忘乘每模式时间及费用。
- 对 K 模式分别扫完整网格却称 O(RC)。
- S/D 计费口径不清。
- 用普通 BFS 处理正的转弯成本。
继续深挖
- 加转弯费用后状态怎么改？
- 允许一次换乘且有固定换乘时间怎么求？
- 多模式同时间同费用如何稳定选？
- 动态封路后是否可复用旧路径？
