BFS 求网格上马步最短路，首次到达草地即最少跳跃次数。
OJ: roj
题目 ID: 3080
难度:普及-
标签:搜索BFS最短路网格队列python
创建: 2026-10-01 15:14
更新: 2026-10-07 13:50
前置题目
luogu P1747好奇怪的游戏A 教的无权图最短路 BFS 正是 B 的解法骨架：B 的 main.py 把非障碍格建成无权图后用队列逐层扩展、首次到达 H 即返回层数，只额外叠加障碍过滤、一维下标还原与提前退出，并未用上 A 特有的 12 种走法与反向 BFS，故属模板级复用。roj 1329【例8.2】细胞B 的网格 BFS 直接沿用 A 教的「入队即标记、标记兼作访问、每格至多入队一次」这一状态设计（main.py 里先写 dist[nxt] = dist[pos] + 1 再 append），只是把标记从原地抹 '0' 换成 dist 初值 -1，并叠加马的 8 种跳跃位移与首次够到 H 即最短距离这一判定。roj 1255迷宫问题B 直接复用 A 的「首次到达即最短距离、标记与判重合一份」这一 BFS 核心步骤，只是换成马的 8 位移并把前驱标记换成 dist 数组
题目描述
给定 .、*、K、H。棋子从 K 出发按马走日跳跃，落点需在网格内且非障碍，求到 H 的最少跳跃次数。数据保证有解。
输入：
输出：最少跳跃次数。
思路
把非障碍格看成顶点、马步看成边权为 1 的边，得到无权无向图。BFS 按层扩展，dist 数组兼作判重，首次到达 H 时的层数就是答案。
参考代码
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-10-01 15:14
# update_at: 2026-10-01 15:14
import sys
from collections import deque
from collections.abc import Iterator
START, GOAL, OBSTACLE = b"KH*" # 三个标记的 ASCII 码；bytes 解包出来的就是整数
JUMPS = ( # 马走日的 8 个位移，一行一个家族：先 |dr|=1 的 4 个，再 |dr|=2 的 4 个
(1, 2), (1, -2), (-1, 2), (-1, -2),
(2, 1), (2, -1), (-2, 1), (-2, -1),
)
def neighbours(pos: int, board: bytes, C: int, R: int) -> Iterator[int]:
"""产出 pos 一次跳跃能落到的可行下标：越界或踩到障碍的候选直接不产出。"""
row, col = divmod(pos, C)
for dr, dc in JUMPS:
r, c = row + dr, col + dc
if 0 <= r < R and 0 <= c < C and board[r * C + c] != OBSTACLE:
yield r * C + c
def bfs(board: bytes, C: int, R: int, start: int) -> int:
"""逐层扩展求最短路，返回首次够到草的层数；题目保证有解，故不会走空。"""
dist = [-1] * (C * R) # -1 同时表示"没访问过"和"距离未知"
dist[start] = 0
q = deque([start])
while q:
pos = q.popleft()
for nxt in neighbours(pos, board, C, R):
if dist[nxt] < 0:
if board[nxt] == GOAL: # 先进先出，第一次够到就是最少跳跃次数
return dist[pos] + 1
dist[nxt] = dist[pos] + 1
q.append(nxt)
return -1
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
C, R = int(next(data)), int(next(data))
board = b"".join(next(data) for _ in range(R)) # 逐行拼接，下标即 r * C + c
print(bfs(board, C, R, board.index(START)))
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-06 11:40
* update_at: 2026-10-06 11:40
*/
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXC = 155;
const int MAXR = 155;
int C, R;
char g[MAXR][MAXC]; // 网格地图
int dist[MAXR][MAXC]; // dist[r][c] = 从起点到(r,c)的最少跳跃次数，-1表示未访问
// 马走日的8个位移
const int dr[8] = { 1, 1, -1, -1, 2, 2, -2, -2 };
const int dc[8] = { 2, -2, 2, -2, 1, -1, 1, -1 };
struct Node {
int r, c;
};
queue<Node> q;
int bfs(int sr, int sc) {
memset(dist, -1, sizeof(dist));
dist[sr][sc] = 0;
q.push((Node){sr, sc});
while (!q.empty()) {
Node u = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
int nr = u.r + dr[i];
int nc = u.c + dc[i];
if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; // 越界
if (g[nr][nc] == '*') continue; // 障碍
if (dist[nr][nc] != -1) continue; // 已访问
if (g[nr][nc] == 'H') // 首次到达草地即最少跳跃次数
return dist[u.r][u.c] + 1;
dist[nr][nc] = dist[u.r][u.c] + 1;
q.push((Node){nr, nc});
}
}
return -1; // 题目保证有解，不会走到这里
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> C >> R;
int sr = -1, sc = -1;
for (int i = 0; i < R; i++) {
cin >> g[i];
for (int j = 0; j < C; j++) {
if (g[i][j] == 'K') {
sr = i;
sc = j;
}
}
}
cout << bfs(sr, sc) << "\n";
return 0;
}