一、连通块问题 / 洪水填充（Flood Fill） 典型场景：统计二维网格中连通块数量、最大连通块面积、或改变连通块标记。BFS 使用队列代替递归，避免了递归深度过大的风险。

模板（四方向，统计面积）

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

const int MAXN = 1005;
int n, m;
int grid[MAXN][MAXN];          // 地图，1表示陆地/目标区域
bool vis[MAXN][MAXN];

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

// BFS 返回连通块大小
int bfs(int sx, int sy) {
    queue<pair<int, int>> q;
    q.push({sx, sy});
    vis[sx][sy] = true;
    int area = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        area++;                 // 每出队一个格子，面积加一
        
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 边界检查、障碍检查、未访问检查
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && !vis[nx][ny] && grid[nx][ny] == 1) {
                vis[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    return area;
}

int main() {
    // 输入 n, m, grid ...
    memset(vis, 0, sizeof(vis));
    int blocks = 0, maxArea = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!vis[i][j] && grid[i][j] == 1) {
                blocks++;
                maxArea = max(maxArea, bfs(i, j));
            }
        }
    }
    cout << "连通块数量: " << blocks << endl;
    cout << "最大面积: " << maxArea << endl;
    return 0;
}

模板要点 队列：存储待访问的坐标，queue<pair<int, int>> 或自定义结构体。

入队即标记：在将新格子 push 进队列前就设置 vis[nx][ny] = true，防止同一格子被重复入队。

面积统计：在出队时计数，或入队时计数均可，效果一致。

优势：网格极大时（如 1000×1000），BFS 不会因递归栈溢出，比 DFS 更安全。

二、最小步数 / 最短路径问题 核心思想：BFS 按“距离起点步数”分层扩展，首次到达终点的步数即为最短步数。这是 BFS 最典型的应用。

1. 基础模板：求最短路径长度（无权图）

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

const int MAXN = 1005;
int n, m;
int maze[MAXN][MAXN];          // 0可走，1障碍
int dist[MAXN][MAXN];          // 同时充当 vis 和 距离记录

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

int bfs(int sx, int sy, int ex, int ey) {
    // 初始化距离数组为 -1 表示未访问
    memset(dist, -1, sizeof(dist));
    queue<pair<int, int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        
        // 如果到达终点，直接返回距离（因为 BFS 首次到达即最短）
        if (x == ex && y == ey) {
            return dist[x][y];
        }
        
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && maze[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;  // 无法到达
}

int main() {
    // 输入 n, m, maze, 起点(sx,sy), 终点(ex,ey)
    int steps = bfs(sx, sy, ex, ey);
    if (steps == -1) cout << "无法到达" << endl;
    else cout << "最短步数: " << steps << endl;
    return 0;
}

2. 进阶：记录最短路径本身（前驱节点） 若需要输出具体路径，可维护一个 prev 数组记录每个格子的来源。

pair<int, int> pre[MAXN][MAXN];   // 记录前驱坐标

void printPath(int ex, int ey) {
    vector<pair<int, int>> path;
    int x = ex, y = ey;
    while (pre[x][y] != make_pair(-1, -1)) {  // 起点标记
        path.push_back({x, y});
        auto [px, py] = pre[x][y];
        x = px; y = py;
    }
    path.push_back({x, y});  // 起点
    reverse(path.begin(), path.end());
    for (auto p : path) cout << "(" << p.first << "," << p.second << ") ";
}
在 BFS 扩展时设置前驱：

cpp
if (dist[nx][ny] == -1) {
    dist[nx][ny] = dist[x][y] + 1;
    pre[nx][ny] = {x, y};   // 记录从 (x,y) 到达 (nx,ny)
    q.push({nx, ny});
}

模板要点 距离数组 dist：初始化为 -1，同时承担 vis 功能。

终点判断：在出队时检查终点，可保证最短性；也可在扩展邻居时判断，略微提前。

时间复杂度：每个节点入队一次出队一次，O(V+E)，非常高效。

适用性：仅适用于边权为 1 或边权均等的图。有权图最短路径需用 Dijkstra。

三、综合 BFS 题目 综合题可能涉及多状态、多维度、或带钥匙/门的迷宫等。核心是在 BFS 状态中增加维度来描述不同情形。

示例：带钥匙和门的迷宫（状态压缩 BFS） 题目：网格中有起点、终点、墙、钥匙（a-f）和门（A-F），拿到对应钥匙才能开门。求最短步数。

思路：BFS 的状态不仅是坐标，还有当前持有的钥匙集合（用二进制位表示）。vis[x][y][keys] 三维标记。

struct State {
    int x, y, keys, steps;
};

int bfs(vector<string>& grid, int sx, int sy) {
    int n = grid.size(), m = grid[0].size();
    bool vis[35][35][1 << 6] = {false};  // 假设最多6把钥匙
    queue<State> q;
    q.push({sx, sy, 0, 0});
    vis[sx][sy][0] = true;
    
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    while (!q.empty()) {
        auto [x, y, keys, steps] = q.front(); q.pop();
        
        if (grid[x][y] == 'E') return steps;  // 到达终点
        
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            char c = grid[nx][ny];
            if (c == '#') continue;
            
            int newKeys = keys;
            if (c >= 'a' && c <= 'f') {
                newKeys |= (1 << (c - 'a'));    // 捡钥匙
            }
            if (c >= 'A' && c <= 'F') {
                // 检查是否有对应的钥匙
                if (!(newKeys & (1 << (c - 'A')))) continue;
            }
            
            if (!vis[nx][ny][newKeys]) {
                vis[nx][ny][newKeys] = true;
                q.push({nx, ny, newKeys, steps + 1});
            }
        }
    }
    return -1;
}

其他常见综合 BFS 变种 多起点 BFS：所有起点同时入队，初始距离为 0，常用于“感染传播”或“多元最短路径”。

01 BFS：边权仅为 0 或 1 的最短路，用双端队列 deque 代替普通队列，遇到 0 边权放队首，1 边权放队尾。

双向 BFS：从起点和终点同时 BFS，当两个搜索相遇时结束，常用于状态空间巨大但起点终点明确的问题（如单词接龙）。

四、BFS 与 DFS 对比总结 问题类型 推荐算法 理由 连通块 / Flood Fill 均可 两者时间复杂度相同，BFS 更安全（无栈溢出），DFS 代码更简洁 最短路径 / 最小步数 BFS BFS 首次到达即最优，无需全局比较；DFS 需要搜索所有路径并记录最小值 找一条可行路径 均可 DFS 回溯易输出路径，BFS 需额外记录前驱 排列组合 / 回溯枚举 DFS 回溯树深度优先自然模拟决策过程，BFS 队列会存储大量中间状态，不实用 状态空间搜索（带状态） BFS/DFS 根据需求，求最短路用 BFS，求任意解或遍历所有可能用 DFS