1. 概述
在本篇文章中，我们将讨论骑士在棋盘上的最短路径问题。具体来说，就是在给定大小的棋盘上，从一个起点出发，找到到达目标点所需的最少步数。我们还将介绍一种高效的解决方案，并附上伪代码实现。
这类问题在算法竞赛和面试中较为常见，常使用 BFS（广度优先搜索） 来解决。因为我们要找的是最短路径，而 BFS 正好适用于这种无权图的最短路径查找场景。
2. 问题描述
给定一个大小为 M × N 的棋盘，我们需要找出从起点 (X, Y) 到终点 (S, T) 的骑士移动的最小步数。
骑士的走法是固定的：它每次可以走“日”字型，即：
- 横向移动 2 格，纵向移动 1 格
- 或者横向移动 1 格，纵向移动 2 格
所以，从一个点 (X, Y) 出发，骑士最多有 8 个可能的下一步位置：
[
(X + 2, Y - 1), (X + 2, Y + 1),
(X - 2, Y + 1), (X - 2, Y - 1),
(X + 1, Y + 2), (X + 1, Y - 2),
(X - 1, Y + 2), (X - 1, Y - 2)
]
如下图所示，是一个骑士在棋盘上可能的 8 个移动方向：
需要注意的是，这些新位置必须在棋盘范围内，否则视为无效。
如果无法从起点到达终点，应返回 -1。
3. 解题思路
我们可以将棋盘建模为一个图，每个格子是一个节点，每一步合法的骑士移动是一条边。这样问题就转化为：在图中寻找从起点到终点的最短路径。
解决这类问题最常用的方法是 BFS（广度优先搜索）。BFS 的特点是从起点开始，一层一层向外扩展，直到找到目标节点。这样可以保证第一次到达目标点时的路径是最短的。
BFS 的实现要点：
- 使用一个队列来保存待访问的节点
- 使用一个二维数组
visited来记录哪些位置已经被访问过 - 使用另一个二维数组
KMove来记录到达每个位置所需的步数 - 每次从队列中取出一个位置，尝试向 8 个方向扩展，合法且未访问的位置入队，并更新步数
最终，当找到终点时，返回对应的步数即可。
4. 伪代码实现
以下是该问题的伪代码实现：
algorithm KSPath(M, N, X, Y, S, T):
// M, N = 棋盘大小
// X, Y = 起点坐标
// S, T = 终点坐标
dx <- [-2, -1, 1, 2, -2, -1, 1, 2]
dy <- [-1, -2, -2, -1, 1, 2, 2, 1]
queue <- new Queue
queue.push([X, Y])
visited <- create 2D array of false (size M+1 by N+1)
visited[X][Y] <- true
KMove <- create 2D array of 0 (size M+1 by N+1)
while queue not empty:
current <- queue.pop()
if current == (S, T):
return KMove[S][T]
for i from 0 to 7:
new_x <- current.x + dx[i]
new_y <- current.y + dy[i]
if OnBoard(new_x, new_y, M, N) and not visited[new_x][new_y]:
visited[new_x][new_y] <- true
KMove[new_x][new_y] <- KMove[current.x][current.y] + 1
queue.push([new_x, new_y])
return -1
辅助函数 OnBoard() 的实现：
algorithm OnBoard(k, s, M, N):
if k >= 1 and k <= M and s >= 1 and s <= N:
return true
else:
return false
关键点说明：
dx[]和dy[]是两个方向数组，表示骑士每次移动的偏移量visited[][]防止重复访问KMove[][]记录到达每个点所需的步数queue用于 BFS 的扩展
时间复杂度分析：
由于每个格子最多访问一次，因此总的时间复杂度为 **O(M × N)**。
5. 小结与踩坑提示 ✅⚠️
- ✅ 骑士最短路径问题本质是图上的最短路径问题，使用 BFS 是标准做法
- ✅ 要注意棋盘索引的范围是否从 0 开始还是从 1 开始（本题假设从 1 开始）
- ⚠️ 如果不使用
visited数组，可能会造成无限循环或重复计算，效率极低 - ⚠️ 在 Java 中实现时，可以用
Queue<int[]>来保存坐标对 - ⚠️ 不要忘记边界判断，否则容易越界
6. 总结
本文介绍了骑士在棋盘上从起点到终点的最短路径问题，并提供了一种基于 BFS 的高效解法。通过将棋盘建模为图，我们使用 BFS 算法有效地解决了这个问题。
如果你在算法题或面试中遇到类似问题，记住以下关键词：骑士走法、BFS、最短路径、二维数组、方向数组。熟练掌握这些概念，就能轻松应对这类题目。