BFS 广度优先搜索 · 通用模板

以下模板适用于 90% 以上的 BFS 题目：

1. 状态表示（坐标/楼层/位置）
2. 方向/转移方式（4方向/8方向/上下移动）
3. 合法性判断（边界/障碍物/是否访问过）

一、标准模板（带步数记录）

适用场景：求最短路径、最少步数、最少操作次数

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

// ===== 第1部分：定义状态结构体 =====
// 根据题目修改：坐标用 (x,y)，楼层用 int，多维度用 struct
struct Node {
    int x, y;      // 当前状态
    // 如果有更多维度，在这里添加
};

// ===== 第2部分：定义全局变量 =====
const int MAXN = 1005;        // 根据题目数据范围调整
int dist[MAXN][MAXN];         // 记录步数，-1 表示未访问
// bool vis[MAXN][MAXN];      // 或者用 vis 标记（二选一）
int dx[4] = {1, -1, 0, 0};    // 方向数组
int dy[4] = {0, 0, 1, -1};    // 根据题目修改（4方向/8方向/一维）

// ===== 第3部分：BFS 主函数 =====
void bfs(int sx, int sy) {
    queue<Node> q;
    q.push({sx, sy});         // 起点入队
    dist[sx][sy] = 0;         // 起点步数为 0

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();

        // 【可选】如果到达目标，可以直接返回
        // if (cur.x == ex && cur.y == ey) return;

        // 枚举所有可能的转移方向
        for (int i = 0; i < 4; i++) {        // 方向数量根据题目修改
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            // ===== 合法性判断（三个条件缺一不可）=====
            // 条件1：不能越界
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            // 条件2：不能是障碍物
            if (mp[nx][ny] == '#') continue;
            // 条件3：不能重复访问（第一次到达即最短）
            if (dist[nx][ny] != -1) continue;

            // 记录步数并入队
            dist[nx][ny] = dist[cur.x][cur.y] + 1;
            q.push({nx, ny});
        }
    }
}

// ===== 第4部分：主函数 =====
int main() {
    // 读入数据
    cin >> n >> m;
    // 初始化 dist 为 -1
    memset(dist, -1, sizeof(dist));

    // 调用 BFS
    bfs(sx, sy);

    // 输出结果
    cout << dist[ex][ey] << endl;
    return 0;
}

二、模板变体

变体1：只标记访问，不记录步数

适用场景：连通块大小统计（只问能到达多少个，不问具体步数）

void bfs(int sx, int sy) {
    queue<Node> q;
    q.push({sx, sy});
    vis[sx][sy] = true;       // 只标记，不记录步数
    int cnt = 1;              // 起点也算一个

    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (越界) continue;
            if (障碍物) continue;
            if (vis[nx][ny]) continue;
            vis[nx][ny] = true;
            cnt++;
            q.push({nx, ny});
        }
    }
    cout << cnt << endl;
}

变体2：一维 BFS

适用场景：楼层问题、数字变换问题

void bfs(int start, int target) {
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == target) return;

        // 枚举所有可能的转移
        int nxt1 = cur + k[cur];   // 上
        int nxt2 = cur - k[cur];   // 下

        if (nxt1 >= 1 && nxt1 <= n && dist[nxt1] == -1) {
            dist[nxt1] = dist[cur] + 1;
            q.push(nxt1);
        }
        if (nxt2 >= 1 && nxt2 <= n && dist[nxt2] == -1) {
            dist[nxt2] = dist[cur] + 1;
            q.push(nxt2);
        }
    }
}