AcWing 1106. 山峰和山谷
原题链接
中等
作者:
十六
,
2021-01-12 16:52:10
,
所有人可见
,
阅读 239
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3+10;
typedef pair<int, int> PII;
int n, ansf, ansg;
int g[MAX][MAX];
bool v[MAX][MAX];
PII q[MAX*MAX];
void bfs(int r, int c, bool& hh, bool& hl){
int h = 0, t = 0;
q[h] = {r, c};
v[r][c] = true;
while(h<=t){
PII tmp = q[h++];
r = tmp.first, c = tmp.second;
for(int i=-1; i<2; i++){
for(int j=-1; j<2; j++){
if(i==0 && j==0) continue;
int rr = r + i, cc = c + j;
if(rr<0 || rr>=n || cc<0 || cc>=n) continue;
//if(rr<0 || rr>=n || cc<0 || cc>=n || v[rr][cc]) continue; 这是错的,因为后面要处理是不是山峰或山谷的问题
if(g[r][c]==g[rr][cc] && !v[rr][cc]){
v[rr][cc] = true;
q[++t] = {rr, cc};
}
if(g[r][c]<g[rr][cc]) hh = true;
if(g[r][c]>g[rr][cc]) hl = true;
}
}
}
}
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(!v[i][j]){
bool hh = false, hl = false; //hh表示有比它高的位置 hl表示有比它低的位置
bfs(i, j, hh, hl);
if(!hl) ansg++;
if(!hh) ansf++;
}
}
}
cout<< ansf<< " "<< ansg<< endl;
return 0;
}