题目重点：Salesforce MTS 面经给棋盘起终点和骑士最少步数；本文将每格建成无权图，说明 BFS 最短性、状态规模及小棋盘不可达情况。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版接受正整数 rows/cols 和零基坐标 (row,col)，棋盘无障碍，骑士每步按 (±2,±1) 或 (±1,±2) 移动且不能出界。
- 起终点相同返回 0，不可达返回 -1；非法尺寸或界外点抛错。题目没有约定这些接口细节。
- 每步代价相同，所以可以用普通 BFS；若不同落点有不同代价，要换 Dijkstra 等有权最短路算法。
解题路线
- 将每个棋盘格视为图节点，合法骑士跳跃视为单位权边。用队列从起点逐层扩展，入队时记录 seen，避免同一格重复入队。
- 队列中存位置与距离。首次出队目标即返回距离：BFS 保证距离 d 的所有可达格都在距离 d+1 之前处理，所以不会存在未发现的更短路线。
- 若队列耗尽仍未见目标，说明在给定棋盘边界内不可达。小棋盘容易出现这种情形，不可用无限棋盘公式直接套。
手动走一遍
8×8 空棋盘，从 (0,0) 到 (1,2) 一步可达，返回 1；起终点都是 (0,0) 返回 0。若棋盘只有 1×3，骑士无法作合法跳跃，从 (0,0) 到 (0,2) 返回 -1。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
MOVES = ((2, 1), (2, -1), (-2, 1), (-2, -1),
(1, 2), (1, -2), (-1, 2), (-1, -2))
def knight_min_moves(rows: int, cols: int, start: tuple[int, int], goal: tuple[int, int]) -> int:
"""Minimum knight moves on an empty board, or -1 if unreachable."""
if rows <= 0 or cols <= 0:
raise ValueError("board dimensions must be positive")
if any(not (0 <= r < rows and 0 <= c < cols) for r, c in (start, goal)):
raise ValueError("start and goal must be on the board")
queue = deque([(start, 0)])
seen = {start}
while queue:
(row, col), distance = queue.popleft()
if (row, col) == goal:
return distance
for dr, dc in MOVES:
next_pos = row + dr, col + dc
if 0 <= next_pos[0] < rows and 0 <= next_pos[1] < cols and next_pos not in seen:
seen.add(next_pos)
queue.append((next_pos, distance + 1))
return -1
复杂度
R×C 个格子，每格最多检查 8 个跳跃，时间 O(RC)，seen 与队列最坏占 O(RC)。若只需大空棋盘两点的步数，可研究几何公式，但题目给 BFS，有限边界下公式要特别验证。
易错点与追问
容易失分的边界
- 误把骑士当作国王的八邻格或只列出四个跳跃方向。
- 出队后才标记 seen，导致同一格在同层被重复入队，浪费时间与内存。
- 不检查行列范围，负下标在 Python 中可能错误地访问棋盘末端。
- 假设所有有限棋盘上的两个合法格都互相可达，漏掉窄棋盘边界。
继续深挖
- 若棋盘有障碍，只过滤被阻塞的目标格；无权条件不变仍可 BFS。
- 若棋盘很大但只求单对点，可讨论双向 BFS，并说明两个搜索前沿如何相遇及复杂度收益依赖形状。
- 若每格移动成本不同，如何把队列换成按累计成本排序的优先队列并处理非负权？
