算法学习系列（四十一）：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 second

const 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 second

const 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 second

const 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;
}