我的世界fabric转换为forge
文章目录
- 一、bfs的Floodfill算法
- 二、使用步骤
- 1.acwing 池塘计数
- 2、Acwing1098. 城堡问题
- 3、AcWing 1106. 山峰和山谷
一、bfs的Floodfill算法
Floodefill算法即填充算法，算法原理就是从一个点开始向四周扩散，向周围可以走到的点填充颜色，直到将可扩散到的点全部填充颜色
二、使用步骤
1.acwing 池塘计数
农夫约翰有一片 N∗M 的矩形土地。
最近，由于降雨的原因，部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内，如果包含雨水，则用”W”表示，如果不含雨水，则用”.”表示。
现在，约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘，即矩阵中共有多少片相连的”W”块。
输入格式
第一行包含两个整数 N 和 M。
接下来 N 行，每行包含 M 个字符，字符为”W”或”.”，用以表示矩形土地的积水状况，字符之间没有空格。
输出格式
输出一个整数，表示池塘数目。
数据范围
输入样例：
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点位置标记，防止返回时重复搜索，
代码如下（示例）：
2、Acwing1098. 城堡问题
题目
1 2 3 4 5 6 7 ############################# 1 # | # | # | | # #####---#####---#---#####---# 2 # # | # # # # # #---#####---#####---#####---# 3 # | | # # # # # #---#########---#####---#---# 4 # # | | | | # # ############################# (图 1) # = Wall | = No wall - = No wall 方向：上北下南左西右东。图1是一个城堡的地形图。
请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。
城堡被分割成 个方格区域，每个方格区域可以有0~4面墙。
注意：墙体厚度忽略不计。
输入格式
第一行包含两个整数 m和 n，分别表示城堡南北方向的长度和东西方向的长度。
接下来 行，每行包含
每个方块中墙的特征由数字 来描述，我们用 1 表示西墙，2 表示北墙，4 表示东墙，8 表示南墙，
例如，如果一个方块的 为 3，则 3 = 1 + 2，该方块包含西墙和北墙。
城堡的内墙被计算两次，方块 (1,1) 的南墙同时也是方块 (2,1) 的北墙。
输入的数据保证城堡至少有两个房间。
输出格式
共两行，第一行输出房间总数，第二行输出最大房间的面积（方块数）。
数据范围
,
解题思路
该题也是简单的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; }3、AcWing 1106. 山峰和山谷
解题思路
这题也是利用floodfill的思想，从第一个点开始扩展到相同的点并放入队列中，遇到不相同的点要和该点比较大小，大的话就maxn ++，否则mini ++；如果 maxn == 0 且 mini ！= 0 则找到了一个山峰，如果 maxn ！= 0 且 mini == 0 则找到了一个山谷，如果maxn ==0 且 mini == 0 则该连通块既是山谷又是山峰；
代码如下
未完待续~