bfs floodfill 算法_floodfill bfs

1   2   3   4   5   6   7  
1

#############################
1 # | # | # | | #
#####—#####—#---#####—#
2 # # | # # # # #
#—#####—#####—#####—#
3 # | | # # # # #
#—#########—#####—#---#
4 # # | | | | # #
#############################
(图 1)

= Wall

| = No wall

• = No wall

方向：上北下南左西右东。

图1是一个城堡的地形图。

请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。

城堡被分割成 m∗n

个方格区域，每个方格区域可以有0~4面墙。
输入格式

第一行包含两个整数 m
和 n

，分别表示城堡南北方向的长度和东西方向的长度。

接下来 m
行，每行包含 n

个整数，每个整数都表示平面图对应位置的方块的墙的特征。

每个方块中墙的特征由数字 P
来描述，我们用1表示西墙，2表示北墙，4表示东墙，8表示南墙，P

为该方块包含墙的数字之和。

例如，如果一个方块的 P

为3，则 3 = 1 + 2，该方块包含西墙和北墙。

城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。

输入的数据保证城堡至少有两个房间。
输出格式

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

1≤m,n≤50
,
0≤P≤15

输入样例：

4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

输出样例：

5
9

#include<bits/stdc++.h>
using namespace std;
const   int N=55;
#define    x  first 
#define y second
int n,m;
int map1[N][N];
bool st[N][N];
typedef pair<int,int>   PII;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int bfs(int x,int y)
{
    queue<PII>q;
    q.push({x,y});
    st[x][y]=1;
    int area=1;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int tx=t.x+dx[i];
            int ty=t.y+dy[i];
            if(tx<0||ty<0||tx>=n||ty>=m||st[tx][ty])    continue;
            if(((map1[t.x][t.y]>>i)&1)==0)
            {
                q.push({tx,ty});
                st[tx][ty]=1;
                area++;
            }
        }
    }
    return area;
}
int main()
{
    int area=0;
    int cnt=0;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    cin>>map1[i][j];
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
        if(!st[i][j])
        {
            area=max(area,bfs(i,j));
            cnt++;
        }
    }
    cout<<cnt<<endl;
    cout<<area<<endl;
    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