#404. 山峰和山谷

山峰和山谷

山峰和山谷

题目描述

FGD 小朋友特别喜欢爬山,在爬山时研究山峰和山谷。他希望提前知道地图上山峰和山谷的数量。

地图被划分成 n×nn\times n 的网格,每个格子 (i,j)(i,j) 的高度为 w(i,j)w(i,j)。

若两个格子有公共顶点(包括共边),就视为相邻。 因此每个格子最多与上、下、左、右、左上、右上、左下、右下八个方向的格子相邻。

当一个格子集合 SS 满足以下条件时,将其视为一座山峰(或一个山谷):

  1. SS 中所有格子高度相同。
  2. SS 中所有格子通过八方向相邻关系连通。
  3. 对于 SS 中的每个格子,其与 SS 外相邻的所有格子,高度都严格低于 SS 的高度(山峰),或严格高于 SS 的高度(山谷)。
  4. 如果一个连通的等高区域周围不存在其他高度的相邻格子,则它既是山峰也是山谷。

请你计算给定地图中山峰数量与山谷数量。如果所有格子的高度都相同,整个地图既是一座山峰,也是一个山谷。

输入格式

第一行包含正整数 nn,表示地图大小。

接下来 nn 行,每行有 nn 个整数,表示对应格子的高度 ww。

输出格式

输出一行,包含两个整数,依次为山峰数量和山谷数量,以空格分隔。

数据范围

  • 1≤n≤10001\le n\le 1000
  • 0≤w≤1090\le w\le 10^9

输入样例 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。

原题示意图

样例1示意图

样例2示意图