http://ybt.ssoier.cn:8088/problem_show.php?pid=1454
【题目描述】
给定一个 n×nn×n 的网格状地图，每个方格 (i,j)(i,j)有一个高度 wijwij 。如果两个方格有公共顶点，则它们是相邻的。
定义山峰和山谷如下：
均由地图上的一个连通块组成；
所有方格高度都相同；
周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。
求地图内山峰和山谷的数量。特别地，如果整个地图方格的高度均相同，则整个地图既是一个山谷，也是一个山峰。
【输入】
第一行一个整数n（2≤n≤1000）n（2≤n≤1000），表示地图的大小。
接下来 nn 行每行 nn 个整数表示地图。第 ii 行有 nn 个整数 wi1,wi2,…,win(0≤wij≤1000000000)wi1,wi2,…,win(0≤wij≤1000000000)，表示地图第 ii 行格子的高度。
【输出】
输出一行两个整数，分别表示山峰和山谷的数量。
#include <bits/stdc++.h>
using namespace std;
struct node {int x;int y;};
int n,m;
int dir[2][8]={{-1,-1,-1,0,0,1,1,1},{-1,0,1,-1,1,-1,0,1}};
int map1[1023][1223];
bool vis[1023][1223];
int ans1=0;
int ans2=0;
void bfs(int x,int y) {queue<node> q;int ll=x,l=y;vis[x][y] = 1;int flag1=0;int flag2=0;q.push({x,y});while(!q.empty()) {x = q.front().x;y = q.front().y;q.pop();for(int i=0;i<8;i++) {int nx = x+dir[0][i];int ny = y+dir[1][i];if (nx>0 && ny>0 && nx<=n && ny<=n){if (vis[nx][ny]==0) {if (map1[nx][ny]==map1[x][y]) {q.push({nx,ny});vis[nx][ny] = 1;q.push({nx,ny});}}if (map1[nx][ny]>map1[x][y]) {flag1 = 1;}if (map1[nx][ny]<map1[x][y]) {flag2 = 1;}}}}if (flag1==0){ans1++;//cout<<ll<<" "<<l<<" "<<1<<endl;}if (flag2==0){ans2++;//cout<<ll<<" "<<l<<" "<<2<<endl;}}
int main() {cin>>n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin>>map1[i][j];}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (vis[i][j]==0) {bfs(i,j);//cout<<"++"<<endl;}}}cout<<ans1<<" "<<ans2<<endl;return 0;
}