宽度优先搜索（BFS）_C

BFS

Flood Fill（洪水覆盖算法）
- 核心思想
- 实现效果
- 例题
最短距离
最小步数

特点
1.BFS可以求最小，第一次搜到就最小
2.BFS是一个基于迭代的算法，所以他有一个很重要的特点就是，他不会爆栈，这个主要是针对DFS说的，也就是当一个问题的搜索层数可能很深的时候，但是节点个数不深的时候，如过DFS和BFS都可以的话，我们优先选择BFS

Flood Fill（洪水覆盖算法）核心思想

核心思想：从一个起点开始，然后每一次，我们随机选择一个新加进来的格子，然后看一下它周围，能不能扩展新的格子，如果周围能扩展新格子的话，就把他扩展进来，直到整个算法结束（不能扩展新格子为止），这里面需要判重，一个格子只能覆盖一次

实现效果

可以在线性时间复杂度内，找到某个点所在的连通块

这个算法，深搜宽搜都能实现，一般来说是用的宽搜，因为深搜容易爆栈，

例题

池塘计数
做法是什么呢，就是遍历这个图，一行一行扫描，然后发现水，如果还没有被覆盖过，就开始坐flood fill

#include
using namespace std;
#define PII pair<int, int>
#define x first
#define y second
#define endl '\n'
const int N = 1010;
bool st[N][N];
char mp[N][N];
int n, m;

void bfs(int x, int y)
{
    queue<PII> q;
    q.push({x, y});
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        for(int i=t.x-1; i<=t.x+1; i++)
        {
            for(int j=t.y-1; j<=t.y+1; j++)
            {
                if(i == t.x && j == t.y) continue;
                if(i < 1 || i > n || j > m || j < 1) continue;
                if(mp[i][j] == '.' || st[i][j]) continue;
                
                st[i][j] = 1;
                q.push({i, j});
            }
        }
    }
}


int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        for(int j=1; j<=m; j++)
        {
            scanf(" %c", &mp[i][j]);
        }
    }
    
    // cout << mp[1][1] << endl;
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        for(int j=1; j<=m; j++)
        {
            if(mp[i][j] == 'W' && !st[i][j]) 
            {
                bfs(i, j);
                // cout << i << ' ' << j << endl;
                cnt ++;
            }
        }
    }
    
    printf("%d\n", cnt);
    return 0;
}