【经典算法】BFS之Flood Fill_floodfill算法就是bfs吗

简述

Flood Fill：字面理解，洪水填充，(大概意思是传播的很快，扩散的广，像水一样四处流动一样)。其实我感觉不就是个BFS嘛，感觉BFS起了个别的名字
大致思想：中间一个点，向四周扩展，每次扩散一圈，下次再一圈…如此下去

我们再想想我们数据结构学的BFS(广度优先遍历)，这不是一回事嘛…

基本的策略： 由于该算法思想是从中心向四周扩展，对于代码上，一般都是用队列来实现，每次从队列中取队头，然后标记该点被遍历后，并将与之相邻的其他点都压入队列中。

再扩展到题，给人的感觉就是需要加判断，不是说每个点四周的所有点都可以Flood Fill

大致模板：

void bfs(int a ,int b){
   
    queue<PAIR> q;
    st[a][b] = true;
    q.push({
   a,b});
    
    while (q.size()){
   
        auto t = q.front();
        q.pop();
        a = t.first , b = t.second;
        st[a][b] = true;
        
        for (a,b)相邻的点{
   
            (x,y) = (a,b)的邻点
            if (x,y没被遍历过){
   
                st[x][y] = true;
                q.push(x,y);
            }
        }
        
 
    }
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

给我的感觉就是BFS，没什么难度，大致就长上面这样，主要是根据题来说灵活多变

池塘计数POJ2386

来源： poj2386

题意： 大致的意思是n*m的单元格，"."表示土地，"W"表示水，对于每个单元格来说，可以跟上、左上、右上、左、右、右下、左下相连，问有多少个池塘(即有多少个连通块是水)。

分析： 对于是水的单元格，进行Flood Fill，向四周扩散，如果四周是陆地，则不能扩散。每一次Flood Fill会填充一块是水的区域(池塘),统计一下有多少池塘即统计对于是水的单元格用了多少次Flood Fill。

复杂度：时间复杂度O(N²)，最坏都要遍历一遍矩阵，空间复杂度O(N²)，Flood Fill我们要记录哪些地方被遍历过了

代码：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int,int> PAIR;
const int N = 1e3 + 10;

int n ,m ;
char g[N][N];
bool st[N][N];//记录该点是否flood fill过

void bfs(int a ,int b){
   
    queue<PAIR> q;
    st[a][b] = true;
    q.push({
   a,b});
    
    while (q.size()){
   
        auto t = q.front();
        q.pop();
        a = t.first , b = t.second;
        st[a][b] = true;
        
        //相邻点的增量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26