广度优先搜索BFS（洛谷官方）

广度优先搜索 BFS（OJ：洛谷）

相关文章推荐：

• （DFS）洛谷八皇后问题 链接
• 搜索题单 DFS（洛谷官方）

目录

• 题目1：P1443 马的遍历
  • 题意概述
  • 思维要点
  • 题解代码
  • 代码要点解析
  • 复杂度分析
  • BFS 模板总结
• 题目2：P1135 奇怪的电梯
  • 题意概述
  • 思维要点
  • 题解代码
  • 代码要点解析
  • 复杂度分析
  • 本题与 BFS 模板的对应关系

题目1：P1443 马的遍历 链接

题意概述

给定一个

n

×

m

n \\times m

n×m 的棋盘，一匹马从起点

(

x

,

y

)

(x, y)

(x,y) 出发，按照象棋中马的走法（"日"字形跳跃），求马到达棋盘上每个点的最少步数。若无法到达，输出

−

1

-1

−1。

思维要点

1. 为什么使用 BFS 而不是 DFS？

核心原理：BFS 按层扩展，第一次到达某个节点时的步数一定是最少步数。

2. vis 数组（访问标记）的必要性

• 在 BFS 中，如果不标记已访问的节点，同一个节点会被重复入队，导致：
  • 无限循环（节点之间互相跳转）
  • 内存溢出（队列无限增长）
  • 结果错误（步数被覆盖为非最优值）
• vis[r][c] = 1 表示该点已经被发现（入队），后续不再处理。

3. 马的 8 个跳跃方向

马走"日"字形，共有 8 个方向：

偏移量 dx[] = {-2, -2, +2, +2, +1, -1, +1, -1}
偏移量 dy[] = {-1, +1, -1, +1, +2, -2, -2, +2}

图示（M 为马的位置，* 为可达点）：

. * . * .
* . . . *
. . M . .
* . . . *
. * . * .

4. 下标从 1 开始（base-1）

题目输入行列均从

1

1

1 开始编号，因此数组下标统一使用 1-based，边界判断为 1 ≤ r ≤ n 且 1 ≤ c ≤ m。

题解代码

#include <bits/stdc++.h>
using namespace std;

int dist[405][405]; // 存储起点到每个点的最少步数，-1 表示不可达
bool vis[405][405]; // 标记是否已访问

// 马的 8 个跳跃方向（"日"字形）
int dx[8] = {–2, –2, 2, 2, 1, –1, 1, –1};
int dy[8] = {–1, 1, –1, 1, 2, –2, –2, 2};

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

memset(dist, –1, sizeof(dist)); // 初始化为 -1（不可达）

int n, m;
cin >> n >> m; // n 行 m 列

int sx, sy;
cin >> sx >> sy; // 起点坐标

// BFS 初始化
queue<pair<int, int>> q; // 使用 pair 将行列绑定
q.push({sx, sy});
dist[sx][sy] = 0;
vis[sx][sy] = true;

// BFS 主循环
while (!q.empty()) {
auto [r, c] = q.front(); // C++17 结构化绑定
q.pop();

for (int i = 0; i < 8; i++) {
int nr = r + dx[i];
int nc = c + dy[i];

// 边界检查 + 访问检查
if (nr < 1 || nr > n || nc < 1 || nc > m) continue;
if (vis[nr][nc]) continue;

vis[nr][nc] = true;
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}

// 输出结果
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
printf("%-5d", dist[i][j]); // 左对齐，宽度为 5
}
printf("\\n");
}

return 0;
}

代码要点解析

复杂度分析

• 时间复杂度：$O(n\times m)$
• 空间复杂度：$O(n\times m)$

BFS 模板总结

1. 初始化：起点入队，标记已访问，距离设为 0
2. 循环：队列非空时
a. 取出队首元素
b. 遍历所有相邻状态
c. 若未访问且合法 → 标记、记录距离、入队
3. 输出结果

记住：BFS = 队列 + vis 标记 + 按层扩展 = 无权图最短路的最佳选择

题目2：P1135 奇怪的电梯 链接

题意概述

一栋

N

N

N 层楼的大楼有一部奇怪的电梯。在第

i

i

i 层，电梯只能向上走

K

i

K_i

Ki​ 层或向下走

K

i

K_i

Ki​ 层（不能超出楼层范围

[

1

,

N

]

[1, N]

[1,N]）。给定起点楼层

A

A

A 和终点楼层

B

B

B，求从

A

A

A 到

B

B

B 最少需要按几次按钮。若无法到达，输出

−

1

-1

−1。

思维要点

1. 问题建模

将每一层楼看作图中的一个节点，每层楼的"上"和"下"操作看作两条边（边权为 1）。问题转化为：在一个无权图中，求从节点

A

A

A 到节点

B

B

B 的最短路径，这正是 BFS 的经典应用。

2. 与"马的遍历"的对比

虽然维度和扩展方式不同，但本质相同：无权图上的单源最短路，用 BFS 求解。

3. 特判 A == B

当起点和终点相同时，答案为

0

0

0，不需要按任何按钮。必须在 BFS 之前特判，否则 BFS 循环中不会处理起点本身。

4. 边界条件

每层的移动距离

K

i

K_i

Ki​ 不同，向上到达 cur + K[cur]，向下到达 cur – K[cur]，需要分别检查：

• 向上：nxt <= N
• 向下：nxt >= 1

题解代码

#include <bits/stdc++.h>
using namespace std;

const int M = 205;
int dist[M]; // 存储起点到每层的最少按键次数
bool vis[M]; // 标记是否已访问
int K[M]; // 每层电梯可移动的层数

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, A, B;
cin >> N >> A >> B;

// 特判：起点即终点
if (A == B) {
cout << 0 << endl;
return 0;
}

for (int i = 1; i <= N; i++) {
cin >> K[i];
}

// BFS 初始化
memset(dist, –1, sizeof(dist));
queue<int> q;
q.push(A);
vis[A] = true;
dist[A] = 0;

// BFS 主循环
while (!q.empty()) {
int cur = q.front();
q.pop();

// 两个方向：上和下
int next[2] = {cur + K[cur], cur – K[cur]};

for (int i = 0; i < 2; i++) {
int nxt = next[i];

// 边界检查 + 访问检查
if (nxt < 1 || nxt > N) continue;
if (vis[nxt]) continue;

vis[nxt] = true;
dist[nxt] = dist[cur] + 1;

// 提前终止：到达终点直接输出
if (nxt == B) {
cout << dist[nxt] << endl;
return 0;
}

q.push(nxt);
}
}

// 无法到达
cout << –1 << endl;
return 0;
}

代码要点解析

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

本题与 BFS 模板的对应关系

BFS 模板 本题对应
─────────────────────────────────────────────────
起点入队 楼层 A 入队
标记已访问 vis[A] = true
距离设为 0 dist[A] = 0
取出队首 cur = q.front()
遍历相邻状态 cur + K[cur] 和 cur – K[cur]
未访问且合法 → 标记、记录、入队 边界判断 + vis 检查 + 入队

本题再次验证：只要是无权图求最短路/最少操作次数，首选 BFS。 关键在于正确识别"状态"和"状态之间的转移"。