AcWing 1106. 山峰和山谷
原题链接
中等
作者:
hai阿卢
,
2021-03-07 21:14:52
,
所有人可见
,
阅读 221
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
#define sx first
#define sy second
int n;
int a[N][N];
bool s[N][N];
queue<PII> q;
void Bfs(int x, int y, bool &higher, bool &lower)
{
q.push({x, y});
s[x][y] = true;
while(!q.empty())
{
PII t = q.front();
q.pop();
//遍历(x,y)周围的点
for(int i = t.sx - 1; i <= t.sx + 1; i++)
{
for(int j = t.sy - 1; j <= t.sy + 1; j++)
{
//如果合法则继续判断
if(i > 0 && i <= n && j > 0 && j <= n)
{
if(a[i][j] != a[t.sx][t.sy])
{
//如果判断有点的高度比这个点大,则这个点不是最高点
if(a[i][j] > a[t.sx][t.sy]) higher = false;
//如果比这个点小, 则这个点不是最低点
else lower = false;
}
//如果相等则属于一个连通块
else if(!s[i][j])
{
q.push({i, j});
s[i][j] = true;
}
}
}
}
}
}
int main()
{
cin >> n;
int low = 0, high = 0;//山峰and山谷
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(!s[i][j])
{
//先假设这个点既是山峰也是山谷
bool higher = true, lower = true;
Bfs(i, j, higher, lower);//广度遍历
if(higher) high++;
if(lower) low++;
}
}
}
cout << high << " " << low << endl;
return 0;
}