将棋盘格子建为无权图，利用 BFS 逐层扩展求骑士从起点到终点的最少移动步数。
OJ: roj
题目 ID: 1450
难度:入门
标签:广度优先搜索图论最短路
创建: 2026-09-30 11:11
更新: 2026-10-05 23:56
题目描述
计算国际象棋中骑士（马）从棋盘上一个格子跳到另一个格子所需的最少步数，每步可走 8 个「日」字方向。
输入：第一行是骑士数量
输出：对每个骑士输出一行最少步数；起点与终点相同则输出 0。例如输入棋盘大小 8、起点 0 0、终点 7 0，输出 5；起点 1 1、终点 1 1 则输出 0。
数据范围：
思路
把每个格子看成无权图中的节点，骑士的 8 个马步位移就是边，从起点 BFS 逐层扩展。dist[x][y] 记录到该格子的最少步数，每步代价为 1，所以首次扩展到终点时的距离就是答案；起点等于终点时直接输出 0。复杂度为每次询问
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 11:11
# update_at: 2026-09-30 11:11
import sys
from collections import deque
from functools import cache
KNIGHT_DELTAS = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)) # 马步 8 个方向
@cache
def knight_graph(L: int) -> tuple[tuple[int, ...], ...]:
"""L×L 棋盘的马步邻接表：格子按 (x, y) → x*L+y 展平编号。
同一组询问共享同一个 L，邻接表只建一次，之后每次 BFS 直接走表。
"""
return tuple(
tuple(
(x + dx) * L + y + dy
for dx, dy in KNIGHT_DELTAS
if 0 <= x + dx < L and 0 <= y + dy < L # 落在棋盘外的不建边
)
for x in range(L)
for y in range(L)
)
def knight_steps(L: int, start: int, target: int) -> int:
"""展平下标 start 到 target 的最少马步数；逐层 BFS，首次碰到 target 即最短。"""
if start == target:
return 0
dist = [-1] * (L * L) # -1 = 还没访问过
dist[start] = 0
queue = deque([start])
while queue:
pos = queue.popleft()
step = dist[pos] + 1
for nxt in knight_graph(L)[pos]:
if dist[nxt] < 0:
if nxt == target: # BFS 按层扩展，第一次到达就是最少步数
return step
dist[nxt] = step
queue.append(nxt)
return -1 # L≥4 的完整棋盘马步图连通，不会走到这里
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data) # 骑士数量
out = []
for _ in range(n):
L = next(data) # 棋盘边长
sx, sy, tx, ty = next(data), next(data), next(data), next(data)
out.append(str(knight_steps(L, sx * L + sy, tx * L + ty)))
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 23:55
* update_at: 2026-10-05 23:55
*/
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXL = 305;
int L; // 棋盘大小 L×L
int dist[MAXL][MAXL]; // dist[x][y] 表示起点到 (x,y) 的最少步数，-1 表示未访问
int sx, sy, tx, ty; // 起点与终点坐标
// 骑士的 8 个马步位移
const int fx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int fy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
// BFS 求起点到终点的最少马步数
int bfs() {
if (sx == tx && sy == ty)
return 0; // 起点即终点，0 步
queue< pair<int,int> > q;
memset(dist, -1, sizeof(dist));
dist[sx][sy] = 0;
q.push(make_pair(sx, sy));
while (!q.empty()) {
pair<int,int> cur = q.front();
q.pop();
int x = cur.first, y = cur.second;
// 枚举 8 个马步后继
for (int i = 0; i < 8; ++i) {
int nx = x + fx[i];
int ny = y + fy[i];
if (nx < 0 || nx >= L || ny < 0 || ny >= L)
continue; // 越界跳过
if (dist[nx][ny] != -1)
continue; // 已访问过
dist[nx][ny] = dist[x][y] + 1;
if (nx == tx && ny == ty)
return dist[nx][ny]; // 首次到达终点即最短
q.push(make_pair(nx, ny));
}
}
return -1; // 题目保证连通，不会到这里
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &L);
scanf("%d %d", &sx, &sy);
scanf("%d %d", &tx, &ty);
printf("%d\n", bfs());
}
return 0;
}