AcWing 1106. 山峰和山谷
原题链接
中等
作者:
沙二
,
2021-12-16 17:27:10
,
所有人可见
,
阅读 180
#include<iostream>
#include<cstring>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=1010,M=N*N;
PII q[M];
int h[N][N];
int n;
bool st[N][N];
void bfs(int sx,int sy,bool& has_higher,bool& has_lower)
{
st[sx][sy]=true;
q[0]={sx,sy};
int hh=0,tt=0;
while(hh<=tt)
{
PII t=q[hh++];
for(int i=t.x-1;i<=t.x+1;i++)
{
for(int j=t.y-1;j<=t.y+1;j++)
{
if(i<0||j<0||i>=n||j>=n)continue;
if(i==t.x&&j==t.y)continue;
if(h[i][j]!=h[t.x][t.y])//不等时不需要判断是否走过
{
if(h[i][j]>h[t.x][t.y])has_higher=true;
else has_lower=true;
}
else if(!st[i][j])//实际上就是把两个写在一起了
{
st[i][j]=true;
q[++tt]={i,j};
}
}
}
}
return;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>h[i][j];
}
}
int peak=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)peak++;//这里必须分开写,因为这个连通块可能既是山峰又是山谷
if(!has_lower)valley++;
}
}
}
cout<<peak<<' '<<valley;
return 0;
}