大连市建设工程老网站,网站开发四点注意事项,网站域名空间多少钱,广州网站优化服务商目录 引言一、池塘计数二、城堡问题三、山峰和山谷 引言
关于这个 F l o o d F i l l Flood\ Fill Flood Fill 算法#xff0c;其实我觉得就是一个 B F S BFS BFS 算法#xff0c;模板其实都是非常相似的#xff0c;只不过有些变形而已#xff0c;然后又叫这个名字。关于… 目录 引言一、池塘计数二、城堡问题三、山峰和山谷 引言
关于这个 F l o o d F i l l Flood\ Fill Flood Fill 算法其实我觉得就是一个 B F S BFS BFS 算法模板其实都是非常相似的只不过有些变形而已然后又叫这个名字。关于 B F S BFS BFS 的知识可以参考我之前的博客 BFS博客链接 。因为就是一个 B F S BFS BFS 模型所以该算法还是以讲题为主那么接下来就开始吧。 一、池塘计数
标签BFS、Flood Fill
思路就是一个标准的 B F S BFS 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.husing namespace std;typedef long long LL;
typedef pairint,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;queuePII 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 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.husing namespace std;typedef long long LL;
typedef pairint,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;queuePII 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,j1),(i,j−1),(i,j1),(i1,j−1),
(i1,j),(i1,j1)。我们定义一个格子的集合 S 为山峰山谷当且仅当S 的所有格子都有相同的高度。S 的所有格子都连通。
对于 s 属于 S与 s 相邻的 s′ 不属于 S都有 wsws′山峰或者 wsws′山谷。
如果周围不存在相邻区域则同时将其视为山峰和山谷。
你的任务是对于给定的地图求出山峰和山谷的数量如果所有格子都有相同的高度那么整个地图即是山峰又是山谷。输入格式
第一行包含一个正整数 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.husing namespace std;typedef long long LL;
typedef pairint,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;queuePII 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;
}
