AcWing 1106. 山峰和山谷
原题链接
中等
作者:
当你的眼睛眯着笑
,
2021-04-12 19:57:03
,
所有人可见
,
阅读 283
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010,M=N*N;
bool st[N][N];
int g[N][N];
int n;
int peak;
int valley;
PII q[M];
void bfs(int i,int j,bool &has_lower,bool &has_higher)
{
q[0]={i,j};
st[i][j]=true;
int hh=0;
int 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==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])
{
st[i][j]=true;
q[++tt]={i,j};
}
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&g[i][j]);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(!st[i][j])
{
bool has_lower=false,has_higher=false;
bfs(i,j,has_lower,has_higher);
if(!has_lower) valley++;
if(!has_higher) peak++;
}
}
}
cout<<peak<<' ';
cout<<valley<<endl;
return 0;
}