广度优先搜索（BFS），顾名思义，是一种逐层推进的搜索策略。它利用队列数据结构，从起始节点出发，层层向外扩展，直至找到目标节点或遍历完所有可达节点。我们将通过一个经典的迷宫寻路问题来深入理解BFS。

问题描述

假设我们置身于一个错综复杂的迷宫中，其布局可以通过一个二维网格表示。网格中的每个单元格可以是通路（'.')，障碍物（'#'），起点（'S'）或终点（'T'）。我们的任务是找出从起点到终点的最短路径长度（即最少步数）。

输入格式

输入的第一行为两个整数 n 和 m，分别代表迷宫的行数和列数。

接下来的 n 行，每行包含一个长度为 m 的字符串，描述迷宫的布局。

输出格式

输出一个整数，表示从起点到终点的最短步数。如果无法到达终点，则输出 -1。

示例输入

3 3
S#T
...
...

示例输出

4

示例解析

（此处可配图说明路径）

数据范围

1 ≤ n, m ≤ 100

实现思路

BFS 非常适合解决此类最短路径问题。其核心思想是：

1. 使用一个队列来存储待访问的节点。
2. 将起点加入队列，并标记为已访问。
3. 当队列不为空时，执行以下操作：
   • 从队列头部取出一个节点（当前节点）。
   • 探索当前节点的所有相邻可达节点（上、下、左、右）。
   • 对于每个可达的相邻节点：
     • 如果它未被访问过且不是障碍物：
       • 将其标记为已访问。
       • 如果它是终点，则计算并输出步数，然后结束。
       • 否则，将其加入队列，并记录其步数（当前节点步数 + 1）。
4. 如果队列为空但仍未找到终点，则表示无法到达，输出 -1。

C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

const int MAX_DIM = 100;
char maze[MAX_DIM + 1][MAX_DIM + 1];
bool visited[MAX_DIM + 1][MAX_DIM + 1];

int dx[] = {0, 0, 1, -1}; // 移动方向：右, 左, 下, 上
int dy[] = {1, -1, 0, 0};

int rows, cols;
int startX, startY, endX, endY;

struct State {
    int r, c, steps;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> rows >> cols;

    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            cin >> maze[i][j];
            if (maze[i][j] == 'S') {
                startX = i;
                startY = j;
            } else if (maze[i][j] == 'T') {
                endX = i;
                endY = j;
            }
        }
    }

    queue<State> q;
    q.push({startX, startY, 0});
    visited[startX][startY] = true;

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        if (current.r == endX && current.c == endY) {
            cout << current.steps << endl;
            return 0;
        }

        for (int i = 0; i < 4; ++i) {
            int nextR = current.r + dx[i];
            int nextC = current.c + dy[i];

            if (nextR >= 1 && nextR <= rows && nextC >= 1 && nextC <= cols &&
                maze[nextR][nextC] != '#' && !visited[nextR][nextC]) {
                
                visited[nextR][nextC] = true;
                q.push({nextR, nextC, current.steps + 1});
            }
        }
    }

    cout << -1 << endl; // 无法到达终点
    return 0;
}

BFS 原理总结

1. BFS 从起点开始，逐层扩展可达节点。
2. 通过队列先进先出的特性，保证了探索的广度。
3. 遇到障碍物或已访问过的节点，则跳过。
4. 一旦找到目标节点，由于是逐层搜索，当前路径即为最短路径。
5. 搜索过程中，需要记录每个节点的步数。

BFS 模板（通用结构）

struct Node {
    // 节点状态信息，例如坐标、步数等
    int row, col, dist; 
};

queue<Node> q;
// 初始化起点节点
Node startNode = {start_row, start_col, 0};
q.push(startNode);
// 标记起点为已访问

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

    // 检查是否到达目标
    if (current.row == target_row && current.col == target_col) {
        // 输出答案 current.dist
        return 0;
    }

    // 遍历相邻节点
    for (int i = 0; i < num_directions; ++i) {
        int next_row = current.row + dr[i];
        int next_col = current.col + dc[i];

        // 检查边界、障碍物、是否已访问
        if (is_valid(next_row, next_col) && !is_obstacle(next_row, next_col) && !is_visited(next_row, next_col)) {
            mark_visited(next_row, next_col);
            q.push({next_row, next_col, current.dist + 1});
        }
    }
}

// 如果循环结束仍未找到目标，则输出 -1

注意事项

• BFS 的核心在于队列的使用。
• 需要维护一个"已访问"的标记，以避免重复访问和陷入死循环。
• 对于网格类问题，通常需要定义好方向向量（如 dx, dy）。
• 确保边界条件的检查准确无误。