广搜BFS基础

一、BFS 核心概念

BFS 是 Breadth-First Search（广度优先搜索）的缩写，也称为「宽度优先搜索」「层次遍历」。

1. 核心思想

从起始节点出发，先遍历完当前节点的所有相邻节点（同一层节点），再依次遍历下一层节点，如同「水波扩散」一般逐层推进。

• 对应马的遍历：从起始棋盘位置出发，先遍历所有一步能跳到的位置（同一层），再遍历所有两步能跳到的位置（下一层），最终得到到达每个位置的最短步数（马走日的最短路径）。
• 对应拯救oibh总部（迷宫最短路径）：从起点出发，先遍历所有相邻的可通行格子（同一层，一步到达），再遍历这些格子的相邻可通行格子（下一层，两步到达），第一次到达终点（oibh总部）的层数就是最短步数。
• 对应最短路径题目（如FJ追牛、流星雨）：每一层对应「一步操作」，第一次到达目标节点时的层数，就是最短步数（BFS 天然适合求解无权图/无代价场景的最短路径）。

2. 关键特性

1. 完备性：只要目标节点存在，BFS 一定能找到它（前提是遍历范围覆盖目标节点）。
2. 最优性：在无权图中，BFS 找到的第一条路径一定是最短路径（步数最少、路径长度最短）。
3. 数据结构依赖：依赖「队列（Queue）」实现，利用队列「先进先出（FIFO）」的特性，保证节点按「层次」入队和出队。
4. 去重需求：必须通过「访问标记数组」避免节点重复入队，否则会出现无限循环、时间复杂度爆炸的问题（如马的遍历中标记已访问的棋盘位置，避免重复计算步数）。

3. 信奥赛常见应用场景

1. 连通块计数（如细胞计数、扫雷空块统计）。
2. 无权图最短路径（如马的遍历、拯救oibh总部、FJ追牛、流星雨安全路径）。
3. 层次遍历问题（如二叉树层次遍历、矩阵的逐层扩散）。
4. 寻找满足条件的最浅节点（如最早到达的安全格子）。

二、BFS 常用核心模版代码（信奥赛标准版）

BFS 模版分为「基础四连通（拯救oibh总部）」和「扩展特殊方向（马的遍历）」，核心结构一致，仅方向数组不同，以下提供 C++ 版本（信奥赛主流语言），兼顾简洁性和可扩展性。

1. 模版核心结构（必背，以拯救oibh总部为例）

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

const int N = 1005; // 根据题目数据规模调整，略大于最大值即可

// 1. 方向数组（核心：四连通/特殊方向，按需选择）
// 四连通（上下左右，对应拯救oibh总部（迷宫））
const int dir4[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
// 马的遍历特殊方向（马走日，8个方向，对应马的遍历）
const int horse_dir[8][2] = {{-2,-1}, {-2,1}, {-1,-2}, {-1,2},
                             {1,-2},  {1,2},  {2,-1},  {2,1}};

bool vis[N][N]; // 2. 访问标记数组：标记节点是否已被处理，避免重复入队
int dis[N][N];  // 距离数组：记录到达每个节点的最短步数（可选，用于马的遍历/迷宫）
int n, m; // 矩阵规模（行、列），按需调整

// 3. BFS 核心函数（以二维矩阵为例，一维问题可简化）
// 参数：起始节点坐标 (x, y)（按需添加其他参数，如终点坐标）
void bfs(int x, int y) {
    // 4. 初始化队列：存储节点状态（二维矩阵常用 pair，带步数可直接用 dis 数组）
    queue<pair<int, int>> q;
    q.push({x, y}); // 起始节点入队
    vis[x][y] = true; // 标记起始节点已访问
    dis[x][y] = 0; // 起始节点步数为 0

    // 5. 队列循环处理：直到队列为空（所有可达节点处理完毕）
    while (!q.empty()) {
        // 6. 取出队首节点（当前处理节点）
        auto cur = q.front();
        q.pop();
        int cx = cur.first; // 当前节点 x 坐标
        int cy = cur.second; // 当前节点 y 坐标

        // 7. 遍历所有方向，扩展相邻节点
        for (int i = 0; i < 4; ++i) { // 马的遍历改为 i < 8，对应 horse_dir
            int nx = cx + dir4[i][0]; // 相邻节点 x 坐标
            int ny = cy + dir4[i][1]; // 相邻节点 y 坐标

            // 8. 合法性判断（核心三要素，按需调整）
            // 要素1：边界合法（不越界，符合题目数据范围）
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            // 要素2：未被访问（去重，避免重复入队）
            if (vis[nx][ny]) continue;
            // 要素3：符合题目条件（如迷宫的「可通行格子」、马的遍历「棋盘内无障碍物」）
            // （注：此部分需根据题目灵活修改，以下为拯救oibh总部示例）
            // if (maze[nx][ny] == 1) continue; // 1 为障碍物，不可通行则跳过

            // 9. 标记访问 + 记录步数 + 入队（核心：入队前必须标记访问，避免重复入队）
            vis[nx][ny] = true;
            dis[nx][ny] = dis[cx][cy] + 1; // 步数 = 当前节点步数 + 1
            q.push({nx, ny});

            // 10. 题目附加逻辑（如最短路径的终点判断、输出结果等）
            // （示例：到达oibh总部（终点 (tx, ty)）直接输出步数并返回）
            // if (nx == tx && ny == ty) {
            //     cout << dis[nx][ny] << endl;
            //     return;
            // }
        }
    }
}

2. 模版变体（带步数的显式存储版）

适用于 FJ 追牛、流星雨等需要统计最短步数的场景，核心仅修改队列存储内容，与上述模版等价：

// 队列存储 (坐标, 步数)
queue<pair<pair<int, int>, int>> q;

// 起始节点入队（初始位置 (x,y)，步数 0）
q.push({{x, y}, 0});
vis[x][y] = true;

// 循环内处理
while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    int cx = cur.first.first;
    int cy = cur.first.second;
    int step = cur.second; // 当前步数

    // 扩展相邻节点时，步数 + 1
    int new_step = step + 1;
    vis[nx][ny] = true;
    q.push({{nx, ny}, new_step});

    // 终点判断
    if (nx == tx && ny == ty) {
        cout << new_step << endl;
        return;
    }
}

3. 针对性模版示例

（1）拯救oibh总部（四连通迷宫最短路径）

核心：方向数组用dir4，合法性判断增加「障碍物过滤」，终点到达即输出结果。

（2）马的遍历（特殊8方向最短步数）

核心：方向数组用horse_dir，dis数组记录每个棋盘位置的最短步数，最终遍历输出整个棋盘的dis数组即可。

三、BFS 注意事项（信奥赛避坑指南）

1. 方向数组的选择与边界判断

   • 四连通（迷宫）、特殊方向（马走日）需根据题目要求选择，切勿混淆（如马的遍历用四连通会完全无法得到正确路径）。
   • 边界判断要严格：二维矩阵注意 nx >= 0、nx < n、ny >= 0、ny < m（避免数组越界 RE），一维问题（如 FJ 追牛）注意非负、不超过最大上限。
   • 示例：拯救oibh总部中若遗漏某一方向（如向上），会导致无法遍历到上方的可通行格子，可能无法到达终点。

2. 访问标记的时机（核心避坑点）

   • 必须在节点入队前标记为已访问，而非节点出队时！
   • 错误原因：若入队前不标记，同一节点可能被多个相邻节点重复入队，导致队列规模爆炸，时间复杂度飙升（如 1000×1000 迷宫可能直接 TLE）。
   • 正确示例：vis[nx][ny] = true; q.push({nx, ny});（先标记，再入队）。

3. 队列的初始化与数据类型

   • 队列存储的内容需根据题目调整：仅需坐标用 pair<int, int>，带步数可用嵌套 pair 或 dis 数组（后者更简洁，适合二维矩阵），复杂状态可用 struct 或 tuple（注意 C++ 版本兼容性）。
   • 大规模数据（如 N=1e5）需注意队列的空间限制，避免 MLE（通常信奥赛题目中 BFS 队列空间足够，无需额外优化）。

4. 特殊情况的优先处理

   • 对于最短路径问题，先处理「直接可达」「无需搜索」的特殊情况，提升效率且避坑。
   • 示例：马的遍历中，若起点与终点重合，直接输出 0；拯救oibh总部中，若起点就是终点，直接输出 0，无需启动 BFS。

5. 数组规模的设置

   • 数组大小需略大于题目给出的最大值（如题目要求 n≤1000，设置 N=1005；题目要求棋盘大小≤200，设置 N=205），避免越界 RE。
   • 原因：BFS 扩散时可能需要遍历整个矩阵，数组过小会导致访问越界。

6. 多组测试用例的数组重置

   • 若题目有多组测试用例，每次 BFS 前必须重置「访问标记数组」和「距离数组」（如 memset(vis, 0, sizeof(vis))、memset(dis, -1, sizeof(dis))），否则会继承上一组数据的标记，导致答案错误。

7. 题目条件的严格匹配

   • BFS 扩展节点时，必须严格判断题目给出的有效条件（如迷宫的「可通行格子」、马的遍历「无棋盘外越界」、流星雨的「安全时间」），遗漏条件会导致遍历无效节点，答案错误或 TLE。

四、BFS 总结（信奥赛核心提炼）

1. 核心三要素：队列（层次遍历）、访问标记（去重）、方向数组（扩展节点），三者缺一不可。
2. 适用场景：无权图最短路径（马的遍历、拯救oibh总部）、连通块计数、层次遍历，是信奥赛中最基础、最常用的搜索算法之一。
3. 解题步骤：
   • 步骤 1：明确题目中的「节点」「相邻节点」「有效条件」（如迷宫的可通行格子、马的合法落点）。
   • 步骤 2：选择合适的方向数组和队列存储结构（如马的遍历用特殊8方向，迷宫用四连通）。
   • 步骤 3：编写 BFS 模版，填充合法性判断和题目附加逻辑（如终点判断、步数记录）。
   • 步骤 4：处理特殊情况，优化效率，避免坑点（如起点终点重合、数组重置）。
4. 经典场景对应：
   • 拯救oibh总部：四连通+BFS最短路径，核心是「障碍物过滤」和「终点快速判断」。
   • 马的遍历：特殊8方向+BFS，核心是「方向数组的正确性」和「距离数组的记录与输出」。
5. 与 DFS 的对比：
   • BFS 适合「最短路径」「连通块计数」，按层次遍历，无栈溢出风险（队列是堆空间）。
   • DFS 适合「枚举所有路径」「深度探索」，递归实现简洁，但存在栈溢出风险（大规模数据需手动模拟栈）。
   • 信奥赛中，BFS 因「最优性」和「稳定性」，在最短路径和连通块问题中优先使用。

关键回顾

• BFS 核心是「层次扩散」，依赖队列实现，访问标记是去重关键。
• 模版的核心结构固定，只需根据题目修改「方向数组」「合法性条件」「附加逻辑」。
• 避坑重点：入队前标记访问、严格边界判断、特殊情况优先处理、方向数组匹配题目要求。

掌握 BFS 模版和注意事项后，能够轻松解决信奥赛中大部分基础搜索问题，后续可结合「双向 BFS」「BFS 优化」等进阶内容，应对更复杂的题目。