算法学习系列（四十一）：Flood Fill算法

引言

关于这个 $FloodFill$ 算法，其实我觉得就是一个 $BFS$ 算法，模板其实都是非常相似的，只不过有些变形而已，然后又叫这个名字。关于 $BFS$ 的知识可以参考我之前的博客： BFS博客链接 。因为就是一个 $BFS$ 模型，所以该算法还是以讲题为主，那么接下来就开始吧。

---

一、池塘计数

标签：BFS、Flood Fill

思路：就是一个标准的 $BFS$ 找连通块的数量，有区别的是这个连通块的标准是八连通的，这个只要在方向上再多设置几个就行了，其余的也没啥了。

题目描述：

农夫约翰有一片 N∗M 的矩形土地。最近，由于降雨的原因，部分土地被水淹没了。现在用一个字符矩阵来表示他的土地。每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。现在，约翰想知道他的土地中形成了多少片池塘。每组相连的积水单元格集合可以看作是一片池塘。每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。输入格式
第一行包含两个整数 N 和 M。接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。输出格式
输出一个整数，表示池塘数目。数据范围
1≤N,M≤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

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1010;int n, m;
char g[N][N];
bool st[N][N];int dir[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};void bfs(PII S)
{st[S.x][S.y] = true;queue<PII> q; q.push(S);while(q.size()){auto t = q.front(); q.pop();for(int i = 0; i < 8; ++i){int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= m) continue;if(st[x][y] || g[x][y] == '.') continue;st[x][y] = true;q.push({x,y});}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < n; ++i) cin >> g[i];int res = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){if(!st[i][j] && g[i][j] == 'W'){res++;bfs({i,j});}}}cout << res << endl;return 0;
}

---

二、城堡问题

标签：BFS

思路：这道题就是求连通块的数量和最大的连通块数，唯一的一个不同就是墙的定义变了，墙是拿一个数来表示的也就是如果为某个特定的数，那么该方向有墙。这个我们可以用位运算，来判定某一位是否为 $1$ ，然后把这个与方向对应就可以了，其余的就跟模板一样了。

题目描述：

    1   2   3   4   5   6   7  #############################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;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 55;int n, m;
int g[N][N];
bool st[N][N];int dir[4][2] = {0,-1,-1,0,0,1,1,0};int bfs(PII S)
{st[S.x][S.y] = true;int cnt = 0;queue<PII> q; q.push(S);while(q.size()){auto t = q.front(); q.pop();cnt++;for(int i = 0; i < 4; ++i){if(g[t.x][t.y] >> i & 1) continue;  // 对应方向有墙int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= m) continue;if(st[x][y]) continue;st[x][y] = true;q.push({x,y}); }}return cnt;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){cin >> g[i][j];}}int res = 0, maxv = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < m; ++j){if(!st[i][j]){res++;maxv = max(maxv, bfs({i,j}));}}}cout << res << endl << maxv << endl;return 0;
}

---

三、山峰和山谷

标签：BFS

思路：就是枚举每一个连通块，然后判断周围是否有比它高，或者低的，如果没有那么就是山峰或者山谷，其余的就是模板。

题目描述：

FGD小朋友特别喜欢爬山，在爬山的时候他就在研究山峰和山谷。为了能够对旅程有一个安排，他想知道山峰和山谷的数量。给定一个地图，为FGD想要旅行的区域，地图被分为 n×n 的网格，每个格子 (i,j) 的高度 w(i,j) 是给定的。若两个格子有公共顶点，那么它们就是相邻的格子，如与 (i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),
(i+1,j),(i+1,j+1)。我们定义一个格子的集合 S 为山峰（山谷）当且仅当：S 的所有格子都有相同的高度。S 的所有格子都连通。
对于 s 属于 S，与 s 相邻的 s′ 不属于 S，都有 ws>ws′（山峰），或者 ws<ws′（山谷）。
如果周围不存在相邻区域，则同时将其视为山峰和山谷。
你的任务是，对于给定的地图，求出山峰和山谷的数量，如果所有格子都有相同的高度，那么整个地图即是山峰，又是山谷。输入格式
第一行包含一个正整数 n，表示地图的大小。接下来一个 n×n 的矩阵，表示地图上每个格子的高度 w。输出格式
共一行，包含两个整数，表示山峰和山谷的数量。数据范围
1≤n≤1000,0≤w≤109
输入样例1：
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
输出样例1：
2 1
输入样例2：
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7
输出样例2：
3 3

示例代码：

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y secondconst int N = 1010;int n;
int h[N][N];
bool st[N][N];int dir[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};void bfs(PII S, bool& has_high, bool& has_low)
{st[S.x][S.y] = true;queue<PII> q; q.push({S.x,S.y});while(q.size()){auto t = q.front(); q.pop();for(int i = 0; i < 8; ++i){int x = t.x + dir[i][0];int y = t.y + dir[i][1];if(x < 0 || x >= n || y < 0 || y >= n) continue;if(h[x][y] > h[t.x][t.y]) has_high = true;if(h[x][y] < h[t.x][t.y]) has_low = true;if(st[x][y] || h[x][y] != h[t.x][t.y]) continue;st[x][y] = true;q.push({x,y});}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){cin >> h[i][j];}}int high = 0, low = 0;for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){if(!st[i][j]){bool has_high = false, has_low = false;bfs({i,j},has_high,has_low);if(!has_high) high++;if(!has_low) low++;}}}cout << high << " " << low << endl;return 0;
}