AcWing 1106. 山峰和山谷
原题链接
中等
作者:
mkuiwu
,
2021-02-10 13:45:54
,
所有人可见
,
阅读 304
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int g[N][N];
queue<PII> q;
int n;
bool st[N][N];
void bfs(int x, int y, bool& has_higher, bool& has_lower ){
q.push({x, y});
st[x][y] = true;
while (!q.empty())
{
auto t = q.front();
q.pop();
int tx = t.first, ty = t.second;
for(int i = tx -1; i <= tx + 1; i++)
for(int j = ty-1; j <= ty+1; j++){
// 1. 判断一些不合法, 不能那么快判断是否遍历过
if(i < 0 || i >= n || j < 0 || j >= n) continue;
if(i == tx && j == ty) continue;
// 2. 如果比当前更高 或更低, 直接改变状态
if(g[i][j] > g[t.first][t.second]) has_higher = true;
else if(g[i][j] < g[t.first][t.second]) has_lower = true;
else if(!st[i][j]){
st[i][j] = true;
q.push({i, j});
}
}
}
}
int main(){
cin >> n;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
scanf("%d", &g[i][j]);
int low_cnt = 0, high_cnt = 0;
bool has_lower = false, has_higher = false;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++){
// 没有被遍历过
if(!st[i][j]){
has_lower = false, has_higher = false;
// 然后开始bfs
bfs(i, j, has_higher, has_lower);
if(!has_higher) high_cnt++;
if(!has_lower) low_cnt++;
}
}
cout << high_cnt << ' ' << low_cnt << endl;
return 0;
}