棋盘上马的最少步数就是隐式无权图的单源最短路：边权全为 1，按步数分层 BFS，首次到达终点即答案。
OJ: roj
题目 ID: 1257
难度:普及-
标签:搜索BFS网格队列python
创建: 2026-09-30 02:01
更新: 2026-10-07 12:15
题目描述
输入
样例：输入 3 / 8 / 0 0 / 7 0 / 100 / 0 0 / 30 50 / 10 / 1 1 / 1 1，输出 5 / 28 / 0。
思路
棋盘是隐式无权图，边权全为 1，用分层 BFS 求最短路：起点距离记 0，出队时把 8 个合法落点中未访问的记为「当前距离 +1」并入队，首次到达终点时的步数就是答案。入队即标记使每格至多扩展一次，复杂度
参考代码
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 02:01
# update_at: 2026-10-14 12:00
import sys
from collections import deque
# 马走日的 8 个偏移：|dr| + |dc| == 3 且两分量都非零，恰好是 (±1, ±2) 与 (±2, ±1)
DIRS = [(dr, dc) for dr in (-2, -1, 1, 2) for dc in (-2, -1, 1, 2) if abs(dr) + abs(dc) == 3] # 8 个马步
def min_knight_steps(size: int, start: tuple[int, int], target: tuple[int, int]) -> int:
"""BFS 求马从 start 到 target 的最少步数；起止相同返回 0。"""
if start == target:
return 0
dist = {start: 0} # tuple 坐标直接当 key，既是距离表也是访问标记
queue = deque([start])
while queue:
r, c = queue.popleft()
step = dist[r, c] + 1 # 出队点的下一层步数
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < size and 0 <= nc < size and (nr, nc) not in dist:
if (nr, nc) == target:
return step # BFS 首次到达即最短
dist[nr, nc] = step
queue.append((nr, nc))
return -1 # 棋盘够大时马必可达，此处仅兜底
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
out: list[str] = []
T = next(data)
for _ in range(T):
size = next(data) # 棋盘边长 L
start = (next(data), next(data)) # 起点 (x, y)
target = (next(data), next(data)) # 终点 (x, y)
out.append(str(min_knight_steps(size, start, target)))
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 07:11
* update_at: 2026-10-05 07:11
*/
// main.cpp：棋盘上马走日的最少步数，按步数分层 BFS 求隐式无权图最短路。
#include <cstdio>
#include <cstring>
typedef long long ll;
const int MAXL = 305;
ll L; // 当前样例的棋盘边长
ll sx, sy, tx, ty; // 起点、终点的坐标
int dr[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; // 马的 8 个走法
int dc[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; // 分别对应 (±1,±2) 与 (±2,±1)
int dist[MAXL][MAXL]; // dist[x][y] = 起点到 (x,y) 的最少步数，-1 表示未访问
struct Node {
ll x;
ll y;
};
Node que[MAXL * MAXL]; // BFS 队列：每格入队即标记，至多入队一次
// 从起点 BFS 到终点，首次到达时的步数即最少步数。
ll bfs() {
if (sx == tx && sy == ty) {
return 0;
}
memset(dist, -1, sizeof(dist));
ll head = 0;
ll tail = 0;
dist[sx][sy] = 0;
que[tail].x = sx;
que[tail].y = sy;
tail++;
while (head < tail) {
ll x = que[head].x;
ll y = que[head].y;
ll step = dist[x][y] + 1; // 出队格子的下一层步数
head++;
for (int k = 0; k < 8; k++) {
ll nx = x + dr[k];
ll ny = y + dc[k];
if (nx < 0 || nx >= L || ny < 0 || ny >= L) continue;
if (dist[nx][ny] != -1) continue;
if (nx == tx && ny == ty) return step; // BFS 首次到达即最短
dist[nx][ny] = step;
que[tail].x = nx;
que[tail].y = ny;
tail++;
}
}
return -1; // 棋盘够大时马必可达，此处仅兜底
}
int main() {
ll T;
scanf("%lld", &T);
for (ll i = 0; i < T; i++) {
scanf("%lld", &L);
scanf("%lld%lld", &sx, &sy);
scanf("%lld%lld", &tx, &ty);
printf("%lld\n", bfs());
}
return 0;
}