文章目录
- 池塘计数
- 城堡问题
- 山峰与山谷
一、池塘计数OJ链接
1.BFS做法
#include <bits/stdc++.h>
#define x first
#define y second
typedef 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 second
typedef 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 second
typedef 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;
}
