本文主要是介绍搜索专项---Flood Fill，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 池塘计数
- 城堡问题
- 山峰与山谷
一、池塘计数OJ链接
1.BFS做法
#include <bits/stdc++.h>#define x first
#define y secondtypedef std::pair<int,int> PII;constexpr int N=1010;int n,m;
char g[N][N];
bool st[N][N];//用来表示已经记录过的
std::queue<PII> q;//用来表示该点已经是土地来遍历周围是否存在土地，如果有加入到队列中int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};void bfs(int ax,int ay)
{q.push({ax,ay});st[ax][ay]=true;while(!q.empty()){PII t=q.front();q.pop();for(int i=t.x-1;i<=t.x+1;i++)for(int j=t.y-1;j<=t.y+1;j++){if (i == t.x && j == t.y) continue;if (i < 0 || i >= n || j < 0 || j >= m) continue;if (g[i][j] == '.' || st[i][j]) continue;q.push({i,j});st[i][j]=true;}}}
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n>>m;for(int i=0;i<n;i++) std::cin>>g[i];int ans=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='W'&&!st[i][j]){bfs(i,j);ans++;}std::cout<<ans<<std::endl;return 0;
}1.DFS做法
#include <bits/stdc++.h>constexpr int N=1010;int n,m;
char g[N][N];
bool st[N][N];int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};void dfs(int x,int y)
{st[x][y]=true;for(int i=0;i<8;i++)if(g[x+dx[i]][y+dy[i]]=='W'&&!st[x+dx[i]][y+dy[i]])dfs(x+dx[i],y+dy[i]);
}
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n>>m;for(int i=0;i<n;i++) std::cin>>g[i];int ans=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='W'&&!st[i][j]){dfs(i,j);ans++;}std::cout<<ans<<std::endl;return 0;
}二、城堡问题OJ链接
1.BFS做法
#include <bits/stdc++.h>#define x first
#define y secondtypedef std::pair<int, int> PII;constexpr int N=55;int n,m;
int g[N][N];
bool st[N][N];
std::queue<PII> q;int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};int bfs(int ax,int ay)
{q.push({ax,ay});st[ax][ay]=true;int area=0;while(!q.empty()){PII t=q.front();q.pop();area++;for(int i=0;i<4;i++){int a=t.x+dx[i],b=t.y+dy[i];if(a<0||a>=n||b<0||b>=m) continue;if(st[a][b]) continue;if(g[t.x][t.y]>>i&1) continue;q.push({a,b});st[a][b]=true;}}return area;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)std::cin>>g[i][j];int cnt=0;int max_area=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(!st[i][j]){cnt++;max_area=std::max(max_area,bfs(i,j));}}std::cout<<cnt<<std::endl;std::cout<<max_area<<std::endl;return 0;
}1.DFS做法
#include <bits/stdc++.h>constexpr int N=55;int n,m;
int g[N][N];
bool st[N][N];
int ans;int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};int dfs(int ax,int ay)
{st[ax][ay]=true;for(int i=0;i<4;i++){int a=ax+dx[i],b=ay+dy[i];if(a<0||a>=n||b<0||b>=m) continue;if(st[a][b]) continue;if(g[ax][ay]>>i&1) continue;ans+=dfs(a,b);}return 1;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n>>m;for(int i=0;i<n;i++)for(int j=0;j<m;j++)std::cin>>g[i][j];int cnt=0,max_area=0;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(!st[i][j]){cnt++;ans=1;dfs(i,j);max_area=std::max(max_area,ans);}std::cout<<cnt<<std::endl;std::cout<<max_area<<std::endl;return 0;
}三、山峰与山谷OJ链接
1.BFS做法
如果在搜索过程中没有出现过比当前点更高的点，则该点及等高点组成山峰。
如果在搜索过程中没有出现过比当前点更低的点，则该点及等高点组成山谷。
#include <bits/stdc++.h>#define x first
#define y secondtypedef std::pair<int,int> PII;constexpr int N=1010;int n;
int g[N][N];
std::queue<PII> q;
bool st[N][N];void bfs(int ax,int ay,bool &has_higher,bool &has_lower)
{q.push({ax,ay});st[ax][ay]=true;while(!q.empty()){PII t=q.front();q.pop();for(int i=t.x-1;i<=t.x+1;i++)for(int j=t.y-1;j<=t.y+1;j++){if(i==t.x&&j==t.y) continue;if(i<0||i>=n||j<0||j>=n) continue;if(g[i][j]!=g[t.x][t.y]){if(g[i][j]>g[t.x][t.y]) has_higher=true;else has_lower=true;}else if(!st[i][j]){q.push({i,j});st[i][j]=true;}}}
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)std::cin>>g[i][j];int peek=0,valley=0;for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(!st[i][j]){bool has_higher=false,has_lower=false;bfs(i,j,has_higher,has_lower);if(!has_higher) peek++;if(!has_lower) valley++;}std::cout<<peek<<" "<<valley<<std::endl;return 0;
}这篇关于搜索专项---Flood Fill的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
