26 · BFS：一层一层地扩散

第 24 节的 DFS 回答的是“能不能走到”。这一节回答“最少几步”。两个问法只差一个字，算法完全不同：DFS 一次沿一条路走到黑，要比较“最少”就得把所有路径长度都试一遍，棋盘上路径数是指数级的；BFS 换一种走法，把距离相同的点攒成一批一起处理，谁先被算出来，谁的答案就是最短的。

• 队列：先进先出。近的点排在前面，这就是“分层”。
• 入队即标记：q.push(v) 的下一句（甚至同一句）就写 dis[v] = dis[u] + 1。等出队才标记，同一个点会被好几个前驱各塞一次。
• dis 初值 −1：−1 同时表示“没到过”。初值用 0 的话，源点（距离 0）和没访问的点分不清。

这一节要新增三样东西：一个容器、一个打包工具、一行批量初始化。先把结构看清楚。

queue<int> q;
q.push(1); q.push(2); q.push(3);      // 从队尾进

while (!q.empty()) {
    int u = q.front();                // ① 先取队首
    q.pop();                          // ② 再删掉它
    cout << u << " ";                 // 输出 1 2 3：先进先出
}

pair<int,int> s = make_pair(3, 5);
cout << s.first << " " << s.second << "\n";     // 3 5

queue<pair<int,int>> q;                 // 存坐标的队列
q.push(make_pair(1, 2));
q.push({3, 4});                         // C++11 写法，等价

pair<int,int> cur = q.front();
int x = cur.first, y = cur.second;      // 拆开用，比每次写 cur.first 清楚

int dis[405][405];
memset(dis, -1, sizeof(dis));     // 全变成 -1：没到过
memset(dis, 0,  sizeof(dis));     // 全变成 0
// memset(dis, 1, sizeof(dis));   // ✗ 每一项会变成 16843009

memset(dis, -1, sizeof(dis));        // ① 所有格子标记为“没到过”
q.push(make_pair(sx, sy));
dis[sx][sy] = 0;                     // ② 源点入队，同一时刻标记

while (!q.empty()) {                 // ③ 一层一层往外扩
    pair<int,int> cur = q.front(); q.pop();
    for (int k = 0; k < 8; ++k) {
        int nx = cur.first + dx[k], ny = cur.second + dy[k];
        // 出界 → 跳过；到过 → 跳过；否则 dis + 1 后入队
    }
}

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

const int MAXN = 405;                // n, m ≤ 400，多留几个位置给边界
int dis[MAXN][MAXN];                 // dis[i][j]：最少步数，-1 表示没到过

const int dx[8] = {1, -1, 2, -2, 1, -1, 2, -2};   // 8 个日字方向，dx[k] 与 dy[k] 配对使用
const int dy[8] = {2, 2, -1, -1, -2, -2, 1, 1};

int main() {
    ios::sync_with_stdio(false);     // 要输出 16 万个数，关同步更稳
    cin.tie(nullptr);

    int n, m, sx, sy;
    cin >> n >> m >> sx >> sy;

    memset(dis, -1, sizeof(dis));    // 全局数组默认是 0，必须显式置 -1

    queue<pair<int, int>> q;
    q.push(make_pair(sx, sy));
    dis[sx][sy] = 0;                 // ★ 入队的同一时刻标记，不等出队

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();                     // front 取值、pop 删除，两句不能合并
        int x = cur.first, y = cur.second;

        for (int k = 0; k < 8; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;  // 跳出棋盘
            if (dis[nx][ny] != -1) continue;                     // 到过，且步数不会更少
            dis[nx][ny] = dis[x][y] + 1;                         // 第一次到 = 最短
            q.push(make_pair(nx, ny));
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cout << dis[i][j] << (j == m ? '\n' : ' ');
        }
    }
    return 0;
}

把“一个源点”改成“很多个源点”，代码只改一处：初始时把所有源点都 push 进队列、dis 都设 0，之后的过程一个字不动。

为什么这样是对的？想象棋盘外有一个虚拟的超级源点 S，它到每个真源点都有一条权为 1 的边。从 S 出发做 BFS，第一层恰好是全部真源点，第二层是“离某个源点 1 步”的格子……把 S 那一层去掉，剩下的就是多源 BFS。所以“每个格子到最近源点的距离”一次 BFS 就能算完，不需要对每个源点各跑一遍。

// k 个源点，一次 BFS 求出每个格子到最近源点的距离
memset(dis, -1, sizeof(dis));
while (k--) {
    int x, y;
    cin >> x >> y;
    dis[x][y] = 0;
    q.push(make_pair(x, y));      // ★ 所有源点一起入队，不是只 push 第一个
}
// 下面的 while (!q.empty()) 与单源 BFS 完全一样

BFS 的三条铁律里，没有一条要求状态必须是格子。只要满足两件事就能用 BFS：状态数量有限、任意两个状态之间的转移代价都是 1。

比如电梯问题：状态是楼层号，转移只有“上 K[u] 层”和“下 K[u] 层”两条。把坐标 + 8 个方向换成楼层 + 2 个方向，模板一个字都不用改。

queue<int> q;                       // 状态只是一个整数，队列就存 int
q.push(A);
dis[A] = 0;

while (!q.empty()) {
    int u = q.front(); q.pop();
    int nxt[2] = { u + K[u], u - K[u] };        // 两条出边
    for (int t = 0; t < 2; ++t) {
        int v = nxt[t];
        if (v < 1 || v > N) continue;           // 出界：这个按钮失灵
        if (dis[v] != -1) continue;             // 已经用更少的步数到过
        dis[v] = dis[u] + 1;
        q.push(v);
    }
}

这就是 BFS 模板的价值：写熟一遍，之后每道题只填两件事——状态是什么、从状态能到哪些状态。其余部分（队列、标记、距离 +1）永远相同。

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

int N, A, B;
int K[205], dis[205];           // 全局数组默认全 0

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

    memset(dis, -1, sizeof(dis));   // -1：这一层还没到过
    queue<int> q;
    q.push(A);
    dis[A] = 0;                     // 起点：0 次按键

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        int nxt[2] = { u + K[u], u - K[u] };     // 上 K[u] 层 / 下 K[u] 层
        for (int t = 0; t < 2; ++t) {
            int v = nxt[t];
            if (v < 1 || v > N) continue;        // 出了大楼：按钮失灵
            if (dis[v] != -1) continue;          // 已经有更少的按键次数了
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
    cout << dis[B] << "\n";
    return 0;
}