Day 20 · BFS 入门：一层一层地扩散

题意：在 n×m 的棋盘上，点 (x, y) 有一匹中国象棋的马。求这匹马走到棋盘上每一个格子最少需要几步。 走不到的格子输出 -1。输出一个 n 行 m 列的矩阵。

思路

1. 写出马的方向数组：马走「日」字，八种走法：dx[8] = {-2,-2,-1,-1,1,1,2,2}， dy[8] = {-1,1,-2,2,-2,2,-1,1}。检查方法：每个方向都是「一个坐标动 2、另一个动 1」。
2. dis 全部初始化成 −1：用 memset(dis, -1, sizeof(dis))。−1 同时表示「没到过」和「到不了」两个意思。
3. 起点入队：push({x, y})，dis[x][y] = 0（马自己所在的位置需要 0 步）。
4. 标准 BFS：出队 → 八个方向 → 越界就跳过 → dis != -1 就跳过 → 否则算距离、入队。
5. 输出矩阵：扫描 n×m 输出 dis[i][j]，到不了的自然还是 −1。

3 3 1 1

0 3 2
3 -1 1
2 1 4

马在 (1,1)，到 (1,2) 要 3 步，到 (2,2) 到不了（3×3 的正中间是马的死穴），所以是 −1。

完整代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int n, m, x, y;
int dis[405][405];          // dis[i][j] = 马到 (i,j) 的最少步数，-1 表示到不了

// ★ 马走「日」字的 8 个方向（一个坐标动 2，另一个动 1）
int dx[8] = {-2, -2, -1, -1,  1, 1,  2, 2};
int dy[8] = {-1,  1, -2,  2, -2, 2, -1, 1};

int main(){
    cin >> n >> m >> x >> y;

    memset(dis, -1, sizeof(dis));       // 先全部设成 -1 = 还没到过（也等于到不了）
    queue<pair<int,int>> q;
    q.push({x, y});
    dis[x][y] = 0;                      // ★ 起点：入队的同时就把距离标记好

    while(!q.empty()){
        pair<int,int> cur = q.front();  // ① 看一眼队头
        q.pop();                        // ② 再删掉它
        int cx = cur.first, cy = cur.second;
        for(int d = 0; d < 8; d++){                   // ★ 马有 8 种走法
            int nx = cx + dx[d], ny = cy + dy[d];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 跳出棋盘了
            if(dis[nx][ny] != -1) continue;                      // ★ 入队时判重
            dis[nx][ny] = dis[cx][cy] + 1;                       // 扩散一层，步数 +1
            q.push({nx, ny});                                    // 入队（和上一句必须挨着）
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(j > 1) cout << " ";      // 数字之间用空格分隔
            cout << dis[i][j];          // 到不了的自然就是 -1
        }
        cout << "\n";
    }
    return 0;
}

0 3 2
3 -1 1
2 1 4

易错点

• 方向数组写错：马是 (2,1) 型而不是 (1,1) 型斜线。漏一个方向会导致大片格子算成 −1。
• dis 没有初始化成 −1：全局数组默认是 0，那样「没到过的点」也会被当成距离 0，全盘皆错。
• 忘记 dis[x][y] = 0：起点会被当成「没到过」，然后又被邻居重新入队，甚至输出 −1。
• 标记时机：一定要在 push 之前/同时设置 dis（见第 3 节）。
• 行末多打空格：用 if(j > 1) cout << " "; 控制，别每行末尾留一个空格。
• 数组开 405×405：n、m 最大 400，下标要到 400，开 405 留余量。

题意：一栋 N 层的楼，第 i 层上写着一个数字 K_i。电梯只有「上」「下」两个有用按钮， 且上下都必须走 K_i 层（在 1 层按「上」就到 1+K₁ 层，按「下」如果超出 1~N 就失灵）。 问从 A 层到 B 层，最少要按几次按钮；到不了输出 −1。

思路

这题是状态抽象的最佳教材：结点不是坐标，而是一个楼层编号。

1. 状态 = 楼层：一共有 N 个状态（1 到 N 层），距离数组只需要一维 dis[205]。
2. 从状态 cur 出发能到哪：两个「方向」——cur + k[cur] 和 cur - k[cur]。
3. 越界判断：nx < 1 || nx > n 就跳过（没有 0 层，也没有 N+1 层）。
4. 标准 BFS：入队时设 dis，dis != -1 就跳过。
5. 答案就是 dis[b]：到不了就还是 −1，直接输出即可，不用特判。

5 1 5
3 3 1 2 5

3

路线：1 层上到 4 层（K₁=3），4 层下到 2 层（K₄=2），2 层上到 5 层（K₂=3），一共按 3 次。

完整代码

#include <iostream>
#include <queue>
using namespace std;

int n, a, b;
int k[205];          // 第 i 层楼上的数字
int dis[205];        // 到第 i 层最少按几次，-1 表示到不了

int main(){
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++){
        cin >> k[i];
        dis[i] = -1;                 // 先全部设成「到不了」
    }

    queue<int> q;                    // ★ 状态就是「楼层」这一个数，所以队列存 int
    q.push(a);
    dis[a] = 0;                      // 起点：入队时同时标记

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        int nxt[2] = {cur + k[cur], cur - k[cur]};   // 「方向」= 上楼 / 下楼
        for(int t = 0; t < 2; t++){
            int nx = nxt[t];
            if(nx < 1 || nx > n) continue;           // 没有 0 层，也没有 N+1 层
            if(dis[nx] != -1) continue;              // 走过了就不再走（K=0 时靠这句防死循环）
            dis[nx] = dis[cur] + 1;
            q.push(nx);
        }
    }

    cout << dis[b] << endl;          // 到不了自然就是 -1，不用特判
    return 0;
}

易错点

• A 等于 B 时答案应为 0。代码里 dis[a] = 0 已经处理好了，但如果忘了给起点设初值就会输出 −1。
• K_i = 0 的楼层：会生成「走到自己」的边，一定要靠 dis != -1 挡掉，否则死循环。
• 越界判断写成 nx <= 0 和 nx >= n：楼层是 1~N，应该是 nx < 1 || nx > n。
• 数组开 [205]：N 最大 200，下标要到 200，开 205 留余量。
• 不要把 k 当成「方向数组」硬塞进 dx/dy：这里每个状态的步长都不同，直接算更清楚。

题意：给一个 n×n 的地图，0 表示马路（可以走），1 表示店铺（不能穿过）。 给出起点 (x₁, y₁) 和车站 (x₂, y₂)，只能上下左右沿着马路走。求走到目的地的最短距离（相邻两格距离为 1）。

思路

这就是「网格 + 边权为 1 + 求最短路」的标准场景，直接用第 3 节的模板套上去：

1. 读地图：逐字符读进 char g[1005][1005]，同时把 dis 全部初始化成 −1。
2. 读起点终点：注意顺序是 x₁ y₁ x₂ y₂（前面是行号，后面是列号）。
3. 起点入队，dis[x1][y1] = 0。
4. 四方向 BFS：遇到 g == '1'（店铺）跳过，遇到 dis != -1（走过）跳过。
5. 输出 dis[x2][y2]：走不到就是 −1。

3
001
101
100
1 1 3 3

4

路径：(1,1) → (1,2) → (2,2) → (3,2) → (3,3)，共 4 步。

完整代码

#include <iostream>
#include <queue>
using namespace std;

int n;
char g[1005][1005];      // '0' 马路，'1' 店铺
int dis[1005][1005];     // ★ 4MB，必须开在全局（写在 main 里会爆栈）

int dx[4] = {0, 0, 1, -1};   // 昨天的方向数组，原封不动
int dy[4] = {1, -1, 0, 0};

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            cin >> g[i][j];       // 逐字符读入，可以跳过换行
            dis[i][j] = -1;       // 顺手初始化成「没到过」
        }

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;   // 起点、终点

    queue<pair<int,int>> q;
    q.push({x1, y1});
    dis[x1][y1] = 0;                  // 起点入队 + 标记

    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();
        int cx = cur.first, cy = cur.second;
        for(int d = 0; d < 4; d++){
            int nx = cx + dx[d], ny = cy + dy[d];
            if(nx < 1 || nx > n || ny < 1 || ny > n) continue;   // 越界
            if(g[nx][ny] == '1') continue;                       // 店铺，不能走
            if(dis[nx][ny] != -1) continue;                      // 已经到过
            dis[nx][ny] = dis[cx][cy] + 1;
            q.push({nx, ny});
        }
    }

    cout << dis[x2][y2] << endl;       // 到不了就是 -1
    return 0;
}

易错点

• 数组开在 main 里面：1000×1000 的 int 数组约 4 MB，局部变量放在栈上会崩，一定要写在所有函数外面（全局）。
• 地图读入方式混乱：cin >> g[i][j] 读字符是安全的；但如果先用 cin >> n 再用 getline，会先读到那个残留的换行符。
• 把 '0'/'1' 当成整数 0/1 比较：地图存的是字符，判断必须写 g[nx][ny] == '1'（带单引号）。
• 终点本身就是店铺：本题数据不保证不会，稳妥起见可以特判；不过按题意车站一定在可到达的位置。
• 起点等于终点：dis 初值是 0，输出 0，正确。

题意：给一个由 0 和 1 组成的 n×n 方阵，其中有一个由 1 构成的闭合圈。 把闭合圈内部的所有 0 都改成 2，其余不变，然后输出整个方阵。

题目给的判断标准很关键：如果从某个 0 出发，只走上下左右、只经过 0，却永远到不了方阵的边界，那它就在圈内。

思路：反过来想，标记「圈外」

直接找「哪些 0 在圈内」很难——你得先知道圈在哪、圈是什么形状。

但反过来想就简单多了：一个 0 只要能从边界走到，它就是圈外的。 而「从边界能走到」正好是一个 BFS 能回答的问题：

1. 把所有边界上的 0 一次性全部入队（第 1 行、第 n 行、第 1 列、第 n 列上的 0），并标记它们「属于圈外」。
2. 从这些起点一起做 BFS，沿着上下左右扩散，凡是能走到的 0 都标记成「圈外」。
3. BFS 结束后，所有没被标记的 0 就是走不到边界的——它们必然在圈内。
4. 输出：1 照抄；0 且被标记 → 输出 0；0 且没被标记 → 输出 2。

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

注意输入的最后两行：第 5 行左边的 1 0 0 0 0 1， 这几个 0 其实是被圈住的（左边被第 5 行第 1 列的 1 挡住、下边被第 6 行挡住），所以它们都被涂成 2。

完整代码

#include <iostream>
#include <queue>
using namespace std;

int n;
int g[35][35];
bool outside[35][35];      // 这格的 0 能不能从边界走到（true = 圈外）

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

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

    // 第一步：把所有边界上的 0 一次性入队（多源 BFS 的「多源」就在这里）
    queue<pair<int,int>> q;
    for(int i = 1; i <= n; i++){
        if(g[i][1] == 0 && !outside[i][1]){ outside[i][1] = true; q.push({i, 1}); }
        if(g[i][n] == 0 && !outside[i][n]){ outside[i][n] = true; q.push({i, n}); }
    }
    for(int j = 1; j <= n; j++){
        if(g[1][j] == 0 && !outside[1][j]){ outside[1][j] = true; q.push({1, j}); }
        if(g[n][j] == 0 && !outside[n][j]){ outside[n][j] = true; q.push({n, j}); }
    }

    // 第二步：从边界一路扩散，能走到的 0 全是「圈外」
    while(!q.empty()){
        pair<int,int> cur = q.front();
        q.pop();
        int cx = cur.first, cy = cur.second;
        for(int d = 0; d < 4; d++){
            int nx = cx + dx[d], ny = cy + dy[d];
            if(nx < 1 || nx > n || ny < 1 || ny > n) continue;   // 越界
            if(g[nx][ny] == 1 || outside[nx][ny]) continue;      // 是墙，或已经标记过
            outside[nx][ny] = true;
            q.push({nx, ny});
        }
    }

    // 第三步：输出。是 1 就照抄；是圈外的 0 也照抄；剩下的 0 全涂成 2
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(j > 1) cout << " ";
            if(g[i][j] == 1) cout << 1;
            else cout << (outside[i][j] ? 0 : 2);
        }
        cout << "\n";
    }
    return 0;
}

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

易错点

• 只从 4 个角出发：圈外的 0 可能只和边上中间的某个 0 连通，角落出发会漏掉一部分，导致把圈外的 0 误涂成 2。要把四条边上的所有 0 都入队。
• 忘记排除墙：扩散时 g[nx][ny] == 1 必须跳过，否则 1 会被当成可通行。
• 输入带空格：本题输入的数字之间有空格，所以用 cin >> g[i][j] 读整数即可（注意别和 P1746 那种无空格字符地图搞混）。
• 输出格式：数字间用空格分隔，行末不要留多余空格。
• 把 outside 反过来理解：它标记的是「圈外」，不是「圈内」，写输出时别弄反。