AcWing1106山峰和山谷

题目描述&＃xff1a;

FGD小朋友特别喜欢爬山&＃xff0c;在爬山的时候他就在研究山峰和山谷。

为了能够对旅程有一个安排&＃xff0c;他想知道山峰和山谷的数量。

给定一个地图&＃xff0c;为FGD想要旅行的区域&＃xff0c;地图被分为 n×n 的网格&＃xff0c;每个格子 (i,j) 的高度 w(i,j) 是给定的。

若两个格子有公共顶点&＃xff0c;那么它们就是相邻的格子&＃xff0c;如与 (i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j&＃43;1),(i,j−1),(i,j&＃43;1),(i&＃43;1,j−1),(i&＃43;1,j),(i&＃43;1,j&＃43;1)

我们定义一个格子的集合 S 为山峰&＃xff08;山谷&＃xff09;当且仅当&＃xff1a;

1. S 的所有格子都有相同的高度。
2. S 的所有格子都连通。
3. 对于 s 属于 S&＃xff0c;与 s 相邻的 s′ 不属于 S&＃xff0c;都有 ws>ws′&＃xff08;山峰&＃xff09;&＃xff0c;或者 ws
4. 如果周围不存在相邻区域&＃xff0c;则同时将其视为山峰和山谷。

你的任务是&＃xff0c;对于给定的地图&＃xff0c;求出山峰和山谷的数量&＃xff0c;如果所有格子都有相同的高度&＃xff0c;那么整个地图即是山峰&＃xff0c;又是山谷。

输入格式

第一行包含一个正整数 n&＃xff0c;表示地图的大小。

接下来一个 n×n 的矩阵&＃xff0c;表示地图上每个格子的高度 w。

输出格式

共一行&＃xff0c;包含两个整数&＃xff0c;表示山峰和山谷的数量。

数据范围

1≤n≤1000,
0≤w≤10^9

输入样例1&＃xff1a;

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8


输出样例1&＃xff1a;

2 1


输入样例2&＃xff1a;

5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7


输出样例2&＃xff1a;

3 3


样例解释

样例1&＃xff1a;

样例2&＃xff1a;

分析&＃xff1a;

本题给定了一个由数字填充的正方形区域&＃xff0c;所有连通的相同的数字构成了一个连通域&＃xff0c;当该连通域的周围数字都小于该连通域数字时&＃xff0c;该连通域就是一个山峰&＃xff0c;当周围数字都大于该连通域数字时&＃xff0c;该连通域就是一个山谷&＃xff0c;当周围即不存在大于连通域数字又不存在小于连通域数字时&＃xff0c;该连通域既是山峰又是山谷&＃xff0c;题目要求我们统计山峰和山谷的数目。

我们只需要在bfs的过程中&＃xff0c;遇见大于连通域数字就说明该连通域不是山峰&＃xff0c;遇见小于连通域数字就说明该连通域不是山谷&＃xff0c;用这样两个标志变量来确定该连通域的性质就可以解决问题了。

#include
#include
using namespace std;
const int N &＃61; 1005;
typedef pair PII;
int g[N][N],n,res1 &＃61; 0,res2 &＃61; 0;
int dx[] &＃61; {0,0,-1,1,-1,-1,1,1};
int dy[] &＃61; {1,-1,0,0,-1,1,-1,1};
bool st[N][N];
PII q[N * N];
void bfs(int x,int y){int hh &＃61; 0,tt &＃61; 0;q[0] &＃61; {x,y};st[x][y] &＃61; true;bool flag1 &＃61; true,flag2 &＃61; true;while(hh <&＃61; tt){PII t &＃61; q[hh&＃43;&＃43;];for(int i &＃61; 0;i <8;i&＃43;&＃43;){int nx &＃61; t.first &＃43; dx[i],ny &＃61; t.second &＃43; dy[i];if(nx <0 || nx >&＃61; n || ny <0 || ny >&＃61; n) continue;if(g[nx][ny] !&＃61; g[t.first][t.second]){if(g[nx][ny] }
int main(){scanf("%d",&n);for(int i &＃61; 0;i }