#404. 山峰和山谷
山峰和山谷
山峰和山谷
题目描述
FGD 小朋友特别喜欢爬山,在爬山时研究山峰和山谷。他希望提前知道地图上山峰和山谷的数量。
地图被划分成 的网格,每个格子 的高度为 。
若两个格子有公共顶点(包括共边),就视为相邻。 因此每个格子最多与上、下、左、右、左上、右上、左下、右下八个方向的格子相邻。
当一个格子集合 满足以下条件时,将其视为一座山峰(或一个山谷):
- 中所有格子高度相同。
- 中所有格子通过八方向相邻关系连通。
- 对于 中的每个格子,其与 外相邻的所有格子,高度都严格低于 的高度(山峰),或严格高于 的高度(山谷)。
- 如果一个连通的等高区域周围不存在其他高度的相邻格子,则它既是山峰也是山谷。
请你计算给定地图中山峰数量与山谷数量。如果所有格子的高度都相同,整个地图既是一座山峰,也是一个山谷。
输入格式
第一行包含正整数 ,表示地图大小。
接下来 行,每行有 个整数,表示对应格子的高度 。
输出格式
输出一行,包含两个整数,依次为山峰数量和山谷数量,以空格分隔。
数据范围
输入样例 1
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
2 1
输入样例 2
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
3 3
提示
可以先用 BFS 或 DFS 搜索每一个极大八方向连通等高区域,然后判断该区域与外界接触的格子中,是否存在更高或更低的格子:
- 不存在更高格子:该区域是山峰;
- 不存在更低格子:该区域是山谷。
注意:对角线接触也算连通;如果整个地图都是同一高度,答案为 1 1。
原题示意图

