认为好的话不妨支持一下( •̀ ω •́ )y

导语

$BFS$ 是搜索的一种方式，其英文全称为 $Breadth$ $First$ $Search$ 。

从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。

$BFS$ 算法在竞赛中主要运用在两种题型：迷宫与连通块。

迷宫

题目描述

一般题目会给出一个长 $n$ ，宽 $m$ 的矩形地图，

地图内的点分为两种，一种为可走，一种为不可走。

给出起点与终点的坐标，求与起点到终点 最短路径的相关内容 。

代码以 Acwing 884.走迷宫 的题目要求为准

代码

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII; //PII将被用来存坐标
const int N = 110;
int n, m;
int g[N][N]; //地图
int dist[N][N]; //g[i][j]表示从起点到坐标为i, j的点的最短距离
bool st[N][N]; //st[i][j]表示坐标为i, j的点是否被搜过
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; //可扩展的方向

int BFS()
{
    queue<PII> q; //用来存待扩展的点
    q.push({0, 0}); //现在我们只发现了起点，其它点都是未知的
    st[0][0] = true; //发现起点了

    while (q.size()) //只要还有发现到的点
    {
        auto t = q.front(); //开始扩展这个发现到的点
        q.pop(); //过河拆桥
        int x = t.first, y = t.second; //这个点的两个坐标

        for (int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i]; //这个点周围点的坐标
            if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 1 || st[a][b] == true) continue;
            //出界、不能走或发现到了，都不用再入队了

            q.push({a, b}); //新的点，加入
            st[a][b] = true; //这个点也被发现了
            dist[a][b] = dist[x][y] + 1; //更新距离
        }
    }

    return dist[n - 1][m - 1]; //终点的坐标为n-1, m-1，返回值是起点到它的最短距离
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            scanf("%d", &g[i][j]);

    printf("%d\n", BFS());

    return 0;
}

连通块

题目描述

一般题目会给出一个长 $n$ ，宽 $m$ 的矩形地图，

地图上的点分为两种，其中有一种是需要我们统计的点。

统计所有连通的点，求 与连通块有关的内容 。

代码以 Acwing 1097.池塘计数 的题目要求为准

#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII; //PII将被用来存坐标
const int N = 1010;
int n, m;
char g[N][N]; //地图
bool st[N][N]; //st[i][j]表示这个点是否拓展过或是否 不 需要拓展
int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};
//可扩展的方向

//大体与迷宫BFS相同，局部有注释
void BFS(int x, int y)
{
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        int cx = t.first, cy = t.second;

        for (int i = 0; i < 8; i ++)
        {
            int a = cx + dx[i], b = cy + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b] == true) continue;
            //由于不需要扩展的'.'在st中已经被标识成了true，所以不需要判断g[a][b]是什么

            q.push({a, b});
            st[a][b] = true;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) scanf("%s", g[i]);

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (g[i][j] == '.')
                st[i][j] = true; //将'.'在st中也标记为true，方便下面的判断和做BFS

    int res = 0;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (!st[i][j])
            {
                BFS(i, j); //将这一池塘的st都标记为true
                res ++; //连通块数量加一
            }

    printf("%d\n", res);

    return 0;
}