广度优先搜索（Breadth First Search, BFS）

广度优先搜索（Breadth First Search, BFS）

BFS算法实现的一般思路为：

// BFS
void BFS(int s){
    queue<int> q;    // 定义一个队列
    q.push(s);        // 队首元素入队

    while (!q.empty()){
        // 取出队首元素top
        // 访问队首元素
        // 将队首元素出队
        // 将top的下一层结点中未曾入队的结点全部入队，并设置为已入队
    }
}

常见题型一：

 代码实现：

#include <stdio.h>
#include <queue>
using namespace std;

const int maxn = 100;

// 位置结构体
struct node{
    int x, y;        // 位置(x, y)
}Node;

int n, m;            // 矩阵大小为 n * m
int matrix[maxn][maxn];        // 01 矩阵
bool inq[maxn][maxn] = { false };    // 记录位置 (x, y) 是否已入过队
int X[4] = { 0, 0, 1, -1 };            // 增量数组
int Y[4] = { 1, -1, 0, 0 };

// 判断坐标(x, y)是否需要访问
bool judge(int x, int y){
    //  越界访问false
    if (x >= m || x < 0 || y >= n || y < 0){
        return false;
    }
    // 当前位置为0或者已经入过队也返回false
    if (matrix[x][y] == 0 || inq[x][y] == true){
        return false;
    }
    // 否则返回 true
    return true;
}

// BFS函数访问位置(x, y)所在的块，将该块的所有'1'的inq都设置为 true
void BFS(int x, int y){
    // 定义一个队列
    queue<node> Q;
    // 队首元素入队
    Node.x = x, Node.y = y;
    Q.push(Node);

    // 队列不为空则一直循环
    while (!Q.empty()){
        // 取出队首元素
        node top = Q.front();
        // 访问队首元素
        // 弹出队首元素
        Q.pop();
        // 将这个元素所相连的坐标设置为已入队
        for (int i = 0; i < 4; i++){
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if (judge(newX, newY)){
                Node.x = newX, Node.y = newY;
                // 将所有相连坐标入队
                Q.push(Node);
                inq[newX][newY] =  true;        // 设置位置[newX, newY]为已入过队
            }
        }
    }
}


int main()
{
    // 读取输入
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            scanf("%d", &matrix[i][j]);        // 读入 01 矩阵
        }
        int ans = 0;    // 存放块数
        // 遍历矩阵
        for (int x = 0; x < m; x++){
            for (int y = 0; j < n; y++){
                // 入过位置为1 且没有入过队则计数器加一
                if (matrix[x][y] == 1 && inq[x][y] == false){
                    ans++;
                    BFS(x, y);
                }
            }
        }
    }

    printf("%d
", ans);

    return 0;
}

常见题型二：

 代码实现：

#include <stdio.h>
#include <queue>
using namespace std;

const int maxn = 100;
struct node{
    int x, y;
    int step;        // step 为从起点到终点位置最少的步数（即层数）
}S, T, temp;

int m, n;        // n 为行， m位列
char maze[maxn][maxn];        // 迷宫信息
bool inq[maxn][maxn] = { false };
int X[4] = { 0, 0, 1, -1 };
int Y[4] = { 1, -1, 0, 0 };

// 检测位置(x, y)是否有效
bool test(int x, int y){
    if (x >= m || x < 0 || y >= n || y < 0)
        return false;
    if (maze[x][y] == '*' || inq[x][y] == true) 
        return false;
    return true;
}

int BFS(){
    queue<node> q;
    q.push(S);

    while (!q.empty()){
        node top = q.front();
        if (top.x == T.x && top.y == T.y)
            return top.step;
        q.pop();
        for (int i = 0; i < 4; i++){
            int newX = top.x + X[i];
            int newY = top.y + Y[i];
            if (test(newX, newY)){
                // 创建一个新结点
                node temp;
                temp.x = newX, temp.y = newY;
                temp.step = top.step + 1;
                q.push(temp);
                inq[newX][newY] = true;
            }
        }
    }
    return -1;
}

int main()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            maze[i][j] = getchar();
        }
        maze[i][n] = '';
    }
    scanf("%d %d %d %d", &S.x, &S.y, &T.x, &T.y);
    S.step = 0;
    printf("%d
", BFS());

    return 0;
}