A 班 第 7 课：专题七·广度优先搜索（BFS）与队列

适用对象： 完成第 6 课（递归与深度优先搜索）的同学 使用方式： 自学讲义，Dev-C++ 5.11，练习按考场 freopen 格式写 学完本课，你应该能：

1. 说清楚 DFS 和 BFS 各自适合什么题，并解释 BFS 为什么天然求最短步数
2. 熟练使用 queue，并默写 BFS 的通用框架
3. 独立完成网格型和状态型两类 BFS 题目

1. 从 DFS 到 BFS：为什么要换一种搜法（10 分钟）

上节课的迷宫题问的是"一共有多少条路"，DFS 一条道走到黑、走不通就回溯，把每条路都数一遍，正合适。

但考场上更常见的问法是："最少要几步"。

这时候 DFS 就尴尬了——它得把所有路径全走完，再从里面挑一条最短的。路径数量是指数级的，稍微大一点的图就直接超时。

BFS 换了个搜法。（BFS 是 Breadth-First Search 的缩写，中文**"广度优先搜索"和"宽度优先搜索"是同一个东西**，两种叫法都常见，题解里遇到别以为是两种算法。）

DFS：像走迷宫的人，一条路走到底，撞墙了退回来换一条
BFS：像往水里扔石头，波纹一圈一圈往外扩，扩到哪算哪

波纹的关键性质：第 k 圈上的所有点，到起点的距离都正好是 k。

所以当波纹第一次碰到终点的时候，那一圈的编号就是答案——而且不用再往下搜了，第一次碰到就一定是最短的，后面再绕过来的路只会更长。

📝 这就是 BFS 的全部价值：它按距离从小到大的顺序访问每个点，因此第一次到达即最短。 DFS 没有这个性质，它的访问顺序和距离毫无关系。

⚠️ "BFS 不回溯"这一条要特别记住。 上节课刚把"选了要还"念了一整课，今天要反过来——BFS 里一个点被标记之后，永远不再取消标记。因为第一次到达它的那条路已经是最短的了，没有任何理由再来第二次。

2. queue：BFS 的专用容器（15 分钟）

DFS 靠递归，系统自动帮你把"还没走完的岔路"记在调用栈里。BFS 没有递归，得自己找个地方存"下一圈要访问的点"——这个地方就是队列。

队列的规矩是先进先出（排队买饭：先来的先打到饭）。这正好对应"先扩到的点先往外扩"，也就是波纹一圈一圈的顺序。

C++ 的队列在 STL 里，bits/stdc++.h 已经把它包含进来了，直接用：

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

int main() {
    queue<int> q;                    // 造一个装 int 的队列

    q.push(10);                      // 入队（从队尾进）
    q.push(20);
    q.push(30);

    cout << q.size() << endl;        // 现在队里有几个
    cout << q.front() << endl;       // 看一眼队头是谁（不删）
    q.pop();                         // 把队头删掉（不返回值）
    cout << q.front() << endl;       // 队头换人了

    while (!q.empty()) {             // 只要队不空就一直取
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
    return 0;
}

输出：

3
10
20
20 30 

五个操作，够用了：

⚠️ front() 和 pop() 是分家的，这是 C++ 容器的统一风格。想"取出队头"必须写两行：

int x = q.front();
q.pop();

只写 q.pop(); 那个值就白白丢了；只写 q.front(); 而不 pop，队头永远不变——这是本课第一大死循环来源。

⚠️ 队列空的时候调用 q.front() 是未定义行为。 它不会报错，会返回一个垃圾值，程序继续若无其事地跑下去，最后给你一个莫名其妙的答案。所以循环条件必须是 while (!q.empty())。

网格题要往队列里塞两个数怎么办

网格上的一个点是 (x, y) 两个数，queue<int> 装不下。用 pair：

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

int main() {
    queue<pair<int, int> > q;        // 装"一对 int"的队列

    q.push({3, 5});                  // 入队时用大括号写一对
    q.push({7, 9});

    int x = q.front().first;         // 取第一个数
    int y = q.front().second;        // 取第二个数
    q.pop();
    cout << x << " " << y << endl;
    return 0;
}

输出：3 5

📝 pair<int, int> 就是"把两个 int 捆成一个"，第一个叫 .first，第二个叫 .second。入队写 q.push({x, y})，取的时候写 q.front().first 和 q.front().second。

（struct 自定义结构体也能达到同样效果，写起来更好读，本课先用 pair，够用。）

动手检查点 1（5 分钟）

新建 check1.cpp：往 queue<int> 里依次放入 1 2 3 4 5，然后每次取出队头，把它输出，如果它是偶数就把它乘 10 再放回队尾，直到队列为空。

输出应该是：1 2 3 4 5 20 40 200 400 2000 4000 20000 40000 …——会一直跑下去。这个"取出来加工完再放回去"的动作，正是 BFS 的核心动作，先熟悉一下手感。（看清楚就 Ctrl+C 停掉。）

3. BFS 通用框架（15 分钟）

跟上节课的 DFS 框架一样，这个也要能默写：

起点入队;
标记起点已访问;  dist[起点] = 0;

while (队列非空) {
    取出队头 x;  弹出;
    for (每一种可能的下一步 y) {
        if (y 越界 或 是障碍 或 已访问) continue;
        标记 y 已访问;
        dist[y] = dist[x] + 1;
        y 入队;
    }
}

和 DFS 框架对着看，就三处不同：

⚠️ 头号坑：标记必须在"入队时"打，不能等"出队时"再打。

想想为什么：一个点可能同时被它的好几个邻居看中。如果只在出队时才标记，那它入队的时候没人拦得住，同一个点会被塞进队列好几次。答案通常还是对的（因为第一次出队时算的仍是最短），但队列会膨胀成好几倍，大数据下直接超时或者爆内存。

📝 口诀：谁入队，谁马上打标记。 写代码的时候，标记 和 push 这两行永远紧挨着，中间不许插别的。

一个数组当两用

BFS 需要两样东西：vis 记录访问过没有，dist 记录距离。其实一个 dist 数组就够了：

把 dist 全部初始化成 -1，dist[i] == -1 就代表"还没访问过"。

memset(dist, -1, sizeof(dist));      // 全部填成 -1

这样判断条件从 if (vis[y]) continue; 变成 if (dist[y] != -1) continue;，少开一个数组，也少一处忘记同步的机会。而且题目要求"到不了输出 -1"的时候，答案已经天然是 -1 了，一个字都不用改。

⚠️ memset 只能用来填 0 和 -1。 填别的数字会得到完全出乎意料的结果（它是按字节填的），要填别的值就老老实实写循环。

4. 例题一：迷宫最短步数（20 分钟）

题面（自编题）： 给一个 n 行 m 列的地图（1 ≤ n, m ≤ 100），0 是空地，1 是障碍。从左上角 (1, 1) 走到右下角 (n, m)，每步只能上下左右移动一格，且只能踩在空地上。求最少步数；走不到输出 -1。保证起点和终点都是空地。

输入样例：
3 4
0 0 1 0
0 0 0 0
0 1 0 0

输出样例：
5

方向数组直接沿用上节课的：

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

int n, m;
int g[105][105];
int dist[105][105];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    memset(dist, -1, sizeof(dist));          // -1 兼作"没访问过"

    queue<pair<int, int> > q;
    q.push({1, 1});                          // ① 起点入队
    dist[1][1] = 0;                          //    起点距离是 0，别忘

    while (!q.empty()) {                     // ② 队不空就一直扩
        int x = q.front().first;
        int y = q.front().second;
        q.pop();                             //    front 和 pop 配套写

        for (int d = 0; d < 4; d++) {        // ③ 试四个方向
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 越界
            if (g[nx][ny] == 1) continue;                         // 障碍
            if (dist[nx][ny] != -1) continue;                     // 来过了
            dist[nx][ny] = dist[x][y] + 1;   // ④ 标记 + 记距离
            q.push({nx, ny});                //    紧挨着入队
        }
    }

    cout << dist[n][m] << endl;              // ⑤ 走不到的话本来就是 -1
    return 0;
}

输出：5

为什么不需要"找到终点就 return"？ 加上当然更快，但没加也完全正确——终点的 dist 在第一次被访问时就已经定死了，后面的搜索再也改不动它。这正是"标记了就不撤"带来的省心。

⚠️ 三个 continue 的顺序不能乱。 必须先判越界，再判障碍和访问过。反过来的话，g[nx][ny] 里的 nx 可能是 -1 或者 101，读到数组外面去了——编译器不报错，运行时可能读到垃圾值，也可能直接崩。上节课的迷宫题也是这个规矩。

动手检查点 2（5 分钟）

把上面的程序原样敲一遍跑通，然后把 dist[nx][ny] = dist[x][y] + 1; 和 q.push({nx, ny}); 之间插一行 cout << nx << "," << ny << " ";，重跑一遍。

你会看到点是按 (1,1) → (1,2)/(2,1) → (2,2) → … 这样一圈一圈冒出来的，而不是像 DFS 那样一头扎到底。亲眼看一次波纹，比背十遍定义管用。

5. 例题二：奇怪的电梯（15 分钟）

BFS 不是网格专用的。只要问题能描述成"从一个状态出发，每次走一步，问最少几步到目标状态"，就能用 BFS，状态是什么都行——楼层号、数字、字符串都可以。

题面（洛谷 P1135 原题）： 一栋 N 层的楼，每层楼 i 上有一个数字 k[i]。在第 i 层按"上"会到 i + k[i] 层，按"下"会到 i - k[i] 层，超出 1 到 N 范围的按钮按不动。现在你在 A 层，要到 B 层，问最少按几次按钮；到不了输出 -1。

输入样例：
5 1 5
3 3 1 2 5

输出样例：
3

（1 层按上到 4 层，4 层按下到 2 层，2 层按上到 5 层，共 3 次。）

状态就是"你在第几层"，一共只有 N 种状态，每种状态有两条出边。整个框架一个字都不用改，只是把二维的 dist[x][y] 换成一维的 dist[x]，把"四个方向"换成"两个按钮"：

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

int n, a, b;
int k[205];
int dist[205];

int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> k[i];

    memset(dist, -1, sizeof(dist));

    queue<int> q;
    q.push(a);
    dist[a] = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        int to[2] = {x + k[x], x - k[x]};    // 两个按钮能到的楼层
        for (int t = 0; t < 2; t++) {
            int y = to[t];
            if (y < 1 || y > n) continue;    // 按钮按不动
            if (dist[y] != -1) continue;     // 来过了
            dist[y] = dist[x] + 1;
            q.push(y);
        }
    }

    cout << dist[b] << endl;
    return 0;
}

输出：3

📝 把这道题和例题一并排放着看——去掉网格的外衣，两段代码是同一个东西。BFS 的模板和"图长什么样"完全无关，你只需要回答两个问题：① 状态怎么表示？② 从一个状态能一步走到哪些状态？

⚠️ 别一看"电梯"就去想模拟或者贪心。 贪心在这题上是错的（有时候要先往远走再绕回来），暴力模拟会走进死循环。"最少按几次"这五个字就是 BFS 的信号。

6. 读错误：3 个典型坑（10 分钟）

错误 1：出队时才标记（本课头号错误）

while (!q.empty()) {
    int x = q.front().first, y = q.front().second;
    q.pop();
    dist[x][y] = ...;                 ← 出队才标记，晚了
    for (int d = 0; d < 4; d++) {
        ...
        q.push({nx, ny});             ← 入队时没打标记
    }
}

同一个格子会被它的多个邻居重复塞进队列。小样例照样输出正确答案，掩盖 bug；到了 n = m = 1000 的测试点，队列里塞进去上百万个重复元素，直接 TLE 或 MLE。

📝 dist[nx][ny] = dist[x][y] + 1; 和 q.push(...) 必须是紧挨着的两行。 检查代码时就盯这两行。

错误 2：q.front() 之后忘了 q.pop()

while (!q.empty()) {
    int x = q.front().first, y = q.front().second;
    // 忘了 q.pop();
    for (...) { ... }
}

队头永远是同一个元素，q.empty() 永远是 false——死循环。表现是程序卡住不动，或者内存一路涨到崩溃。

📝 写 q.front() 的时候，手指顺势就把 q.pop(); 敲出来。 这两个是一对，别拆开。

错误 3：起点忘了初始化

q.push({1, 1});
// 忘了 dist[1][1] = 0;

dist[1][1] 还是 -1，于是起点被当成"没访问过"，它的邻居算出来的距离是 -1 + 1 = 0，整张图的距离全部错位；更糟的是起点会被邻居再次入队，一路死循环下去。

📝 起点的三件事一次做完：push 进队、标记已访问、距离置 0。 三行连着写，一行都不能少。

⚠️ 这三个坑有个共同点：编译器全都不报错，小样例也常常照样过。 交之前一定要自己造一个大一点、不对称的数据跑一遍——上节课的教训，这节课依然适用。

7. 本课练习

⭐ 基础题 1：奇怪的电梯（洛谷 P1135 原题，文件名 t1.cpp，freopen lift.in/lift.out）

题面见上文例题二。1 ≤ N ≤ 200，1 ≤ A, B ≤ N，0 ≤ k[i] ≤ N。

输入样例：
5 1 5
3 3 1 2 5

输出样例：
3

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

int n, a, b;
int k[205];
int dist[205];

int main() {
    freopen("lift.in", "r", stdin);
    freopen("lift.out", "w", stdout);

    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) cin >> k[i];

    memset(dist, -1, sizeof(dist));

    queue<int> q;
    q.push(a);
    dist[a] = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        int to[2] = {x + k[x], x - k[x]};
        for (int t = 0; t < 2; t++) {
            int y = to[t];
            if (y < 1 || y > n) continue;
            if (dist[y] != -1) continue;
            dist[y] = dist[x] + 1;
            q.push(y);
        }
    }

    cout << dist[b] << endl;
    return 0;
}

⭐⭐ 实战题 2：马的遍历（洛谷 P1443 原题，文件名 t2.cpp，freopen horse.in/horse.out）

有一个 n × m 的棋盘（1 ≤ n, m ≤ 400），在某个点 (x, y) 上有一个中国象棋的马。马走"日"字，问它到棋盘上每个点最少要走几步；走不到的输出 -1。

输出 n 行 m 列，每个数占 5 个字符宽度、左对齐。

输入样例：
3 3 1 1

输出样例：
0    3    2    
3    -1   1    
2    1    4    

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

int n, m, sx, sy;
int dist[405][405];
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};

int main() {
    freopen("horse.in", "r", stdin);
    freopen("horse.out", "w", stdout);

    cin >> n >> m >> sx >> sy;
    memset(dist, -1, sizeof(dist));

    queue<pair<int, int> > q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int d = 0; d < 8; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cout << left << setw(5) << dist[i][j];
        cout << endl;
    }
    return 0;
}

       (-2,-1) . (-2,+1)
(-1,-2) .   .   .   (-1,+2)
   .    .   马  .      .
(+1,-2) .   .   .   (+1,+2)
       (+2,-1) . (+2,+1)

⭐⭐⭐ 冲刺题 3：草原起火（自编题，文件名 t3.cpp，freopen fire.in/fire.out）

一片 n × m 的草原（1 ≤ n, m ≤ 500）。地图上 0 是草地，1 是河流（永远烧不着），2 是起火点。所有起火点在第 0 分钟同时开始烧，火每分钟会向上下左右四个方向各蔓延一格（河流挡火）。

输出 n 行 m 列，表示每一格最早在第几分钟被烧到；河流和永远烧不到的地方输出 -1。相邻两数之间用一个空格隔开。

输入样例：
3 4
0 0 1 0
2 0 0 0
0 1 0 2

输出样例：
1 2 -1 2
0 1 2 1
1 -1 1 0

提示： 起火点不止一个，但你只有一个队列。想想框架里"起点入队"那一步，能不能一次入好几个？

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

int n, m;
int g[505][505];
int dist[505][505];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main() {
    freopen("fire.in", "r", stdin);
    freopen("fire.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    memset(dist, -1, sizeof(dist));

    queue<pair<int, int> > q;
    for (int i = 1; i <= n; i++)             // ★ 所有起火点一次性全部入队
        for (int j = 1; j <= m; j++)
            if (g[i][j] == 2) {
                dist[i][j] = 0;
                q.push({i, j});
            }

    while (!q.empty()) {                     // 以下和例题一逐字相同
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if (g[nx][ny] == 1) continue;
            if (dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << dist[i][j];
            if (j < m) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

本课要点速查

queue 五件套：

BFS 通用框架（默写下来）：

起点入队; 标记已访问; dist[起点] = 0;

while (!q.empty()) {
    取队头 x; q.pop();
    for (每一种下一步 y) {
        if (越界 || 是障碍 || dist[y] != -1) continue;
        dist[y] = dist[x] + 1;      // 标记
        q.push(y);                  // 入队，必须紧挨上一行
    }
}

DFS 与 BFS 的分工：

两个常用套路：

dist 兼当 vis：  memset(dist, -1, sizeof(dist));  判断写 dist[y] != -1
                 题目要"到不了输出 -1"时，答案天然就是 -1

多源 BFS：       开跑前把所有起点一次全部入队、全部置 0
                 框架一个字不改，复杂度和单源一样

方向数组模板：

四方向： int dx[4] = {0, 0, 1, -1};   int dy[4] = {1, -1, 0, 0};
马走日： int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
         int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};

易错点： 出队才标记 → 重复入队后 TLE/MLE；front() 后忘 pop() → 死循环；起点忘了置 0 → 全图错位且死循环；越界判断写在读 g[nx][ny] 后面 → 数组越界；memset 只能填 0 和 -1；setw 只管紧跟的一个输出，left 则一直生效。

口诀：入队即标记，标了就不撤；问最少步数，先想 BFS。

以后学： 图的存储（邻接表）与图上的 BFS/DFS、连通块计数、优先队列 priority_queue 与 Dijkstra（边权不都是 1 的最短路）、双向 BFS。今天这个框架到那时候依然一个字不用改——变的只是"从一个状态能走到哪些状态"这一句。

结束前的自我检查

1. 不看讲义，默写 BFS 五步框架，并说出哪两行必须紧挨着写
2. 用一句话说清楚：为什么 BFS 第一次到达终点就一定是最短的，而 DFS 没这个性质
3. 说出 BFS 和 DFS 在"回溯"这件事上为什么正好相反
4. 练习 1、2 全部通过；⭐⭐⭐ 多源 BFS 能独立想出"所有起点一起入队"这一步
5. 把练习 2 的 dist[nx][ny] = dist[x][y] + 1; 挪到出队之后，用 400 400 1 1 跑一遍，亲眼看看程序卡多久（答案还是对的——这正是这个 bug 危险的地方）