bfs的Floodfill算法_floodfill算法例题

---

一、bfs的Floodfill算法

Floodefill算法即填充算法，算法原理就是从一个点开始向四周扩散，向周围可以走到的点填充颜色，直到将可扩散到的点全部填充颜色

二、使用步骤

1.acwing 池塘计数

农夫约翰有一片 N∗M 的矩形土地。

最近，由于降雨的原因，部分土地被水淹没了。

现在用一个字符矩阵来表示他的土地。

每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。

现在，约翰想知道他的土地中形成了多少片池塘。

每组相连的积水单元格集合可以看作是一片池塘。

每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。

请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。

输入格式
第一行包含两个整数 N 和 M。

接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。

输出格式
输出一个整数，表示池塘数目。

数据范围
$1\le N,M\le 1000$
输入样例：
10 12
W…WW.
.WWW…WWW
…WW…WW.
…WW.
…W…
…W…W…
.W.W…WW.
W.W.W…W.
.W.W…W.
…W…W.
输出样例：
3
解题思路：
从输入的第一个点开始判断，如果该点为W且没有走过则开始bfs搜索。bfs搜索时将可走到的W点位置标记，防止返回时重复搜索，
代码如下（示例）：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef pair<int,int> PII;
const int N = 1010;

int n,m,cnt;
queue<PII> q;
bool st[N][N];
char g[N][N];

void bfs(int i,int j)
{
    q.push({i,j});
    st[i][j] = true;//标记一下
    int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
    
    while(q.size())
    {
        PII t = q.front();//拿出队头
        q.pop();
        
        for(int i = 0; i < 8; i ++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(st[x][y]) continue;//走过了，pass
            if(x < 0 ||x >= n || y < 0 || y >= m || g[x][y] == '.')continue;//超过边界和不可走点，pass
            
            st[x][y] = true;//走过的点标记一下
            q.push({x,y});
        }
    }
}

int main()
{
    cin>>n>>m;
    
    for(int i = 0; i < n; i ++)
      for(int j = 0; j < m; j ++)
      cin>>g[i][j];
      
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j ++)
      {
          if(g[i][j] == 'W' && !st[i][j] )//找到第一个点开始搜索，进行四周可走的点进行扩展，直到没有点可走返回
          {                               
             bfs(i,j);
             cnt ++;//返回后找到一个连通块
          }
      }
      
    cout<<cnt;
    return 0;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

2、Acwing1098. 城堡问题

题目

  1   2   3   4   5   6   7  
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #
   #---#########---#####---#---#
 4 #   #   |   |   |   |   #   #
   #############################
           (图 1)

   #  = Wall   
   |  = No wall
   -  = No wall

   方向：上北下南左西右东。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

图1是一个城堡的地形图。
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
城堡被分割成 $m\ast n$ 个方格区域，每个方格区域可以有0~4面墙。
注意：墙体厚度忽略不计。

输入格式

第一行包含两个整数 m和 n，分别表示城堡南北方向的长度和东西方向的长度。
接下来 $m$ 行，每行包含 $n$ 个整数，每个整数都表示平面图对应位置的方块的墙的特征。

每个方块中墙的特征由数字 $P$ 来描述，我们用 1 表示西墙，2 表示北墙，4 表示东墙，8 表示南墙，$P$ 为该方块包含墙的数字之和。

例如，如果一个方块的 $P$ 为 3，则 3 = 1 + 2，该方块包含西墙和北墙。
城堡的内墙被计算两次，方块 (1,1) 的南墙同时也是方块 (2,1) 的北墙。
输入的数据保证城堡至少有两个房间。

输出格式
共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。
数据范围

$1\le m,n\le 50$,
$0\le P\le 15$
解题思路
该题也是简单的floodfill的应用，但特殊一点是对每个方向上有没有墙进行判断。题目规定1 西墙，2 表示北墙，4 表示东墙，8 表示南墙。实际上对应了二进制的0001，0010，0100，1000；所以在进行搜索时，就按照西北东南的循环方向，将循环次数 k 作为g[ i ][ j ]向右移的次数，将结果和1进行按位与，为1 则该房间有墙，0 则没有。

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 51;
typedef pair<int,int> PII;

queue<PII> q;
int n,m,cnt;
int g[N][N];
bool st[N][N];

int bfs(int i ,int j)
{
    q.push({i,j});
    st[i][j] = true;
    int dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0};//注意要根据西北东南的次序
    int res = 1;

    while(q.size())
    {
        PII t = q.front();
        q.pop();
        
       for(int i = 0; i < 4; i ++)
      {
          int x = t.first + dx[i], y = t.second + dy[i];
          if(st[x][y]) continue;
          if(x < 0 ||x >= n || y < 0 || y >= m )continue;
          if(g[t.first][t.second] >> i & 1)continue;
          //判断房间西北东南是否有墙 将g[t.first][t.second]右移 i 次 和 1 按位与 
          //若为1 则该方向有墙，pass
          st[x][y] = true;                         
          q.push({x,y});
          res ++;//面积加一
      }
    }
    return res;
}

int main()
{
    int ans = 0;
    cin >> n >>m;
    
    for(int i = 0; i < n; i ++)
      for(int j = 0; j < m; j ++)
        cin>>g[i][j];
        
    for(int i = 0; i < n; i ++)
      for(int  j = 0; j < m; j ++)
      {
          if(!st[i][j])
          {
             ans = max(bfs(i,j),ans);//找到面积最大值
             cnt ++;//房间数加一
          }
      }
    cout<<cnt<<'\n';
    cout<<ans;
    return 0;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

3、AcWing 1106. 山峰和山谷

题目
题目太长了自己去看

解题思路
这题也是利用floodfill的思想，从第一个点开始扩展到相同的点并放入队列中，遇到不相同的点要和该点比较大小，大的话就maxn ++，否则mini ++；如果 maxn == 0 且 mini ！= 0 则找到了一个山峰，如果 maxn ！= 0 且 mini == 0 则找到了一个山谷，如果maxn ==0 且 mini == 0 则该连通块既是山谷又是山峰；
代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;
typedef pair<int,int> PII;
const int N = 1010;

int n,a,b,res;
int g[N][N];
bool st[N][N];
queue<PII> q;

int bfs(int x,int y)
{
    q.push({x,y});
    st[x][y] = true;
    int maxn = 0,mini = 0;
    int dx[]={-1,-1,-1,0,0,1,1,1},dy[] = {-1,0,1,-1,1,-1,0,1};
    while(q.size())
    {
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 8; i ++)
        {
            int x = t.first + dx[i],y = t.second + dy[i];
            if(x < 0 || x >=n || y < 0 || y >= n) continue;//注意边界
            if(g[x][y] == g[t.first][t.second] && !st[x][y])//找到相同的点加入队列
            {
                q.push({x,y});
                st[x][y] = true;
            }
            
            if(g[x][y] > g[t.first][t.second])//判断大小
            maxn ++;
            else if(g[x][y] < g[t.first][t.second])
            mini ++;
        }
    }
    if(mini == 0 && maxn != 0 )
    return 1;
    if(maxn == 0 && mini != 0 )
    return 2;
    if( mini == 0 && maxn == 0)
    return 3;
    else
    return 0;
}

int main()
{
   
    cin>>n;
    for(int i = 0; i < n; i ++)
      for(int j = 0; j < n; j ++)
        cin >> g[i][j];
        
    for(int i = 0; i < n; i ++)
      for(int j = 0; j < n; j ++)
      {
          if(!st[i][j])//该点没判断过 
          {
            res = bfs(i,j);
          if(res == 1)
          a ++;    //山谷数量
          else if(res == 2)
          b ++;   //山峰数量
          else if(res == 3)
          a++,b++;
          }
          
      }
      cout<<b<<' '<<a;
      return 0;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

未完待续~