#1102. [POI2007]山峰和山谷Grz

[POI2007]山峰和山谷Grz

题目描述

FGD 小朋友特别喜欢爬山,在爬山的时候他就在研究山峰和山谷。为了能够让他对他的旅程有一个安排,他想知道山峰和山谷的数量。

给定一个地图,为 FGD 想要旅行的区域,地图被分为 n×nn\times n 的网格,每个格子 (i,j)(i,j) 的高度 w(i,j)w(i,j) 是给定的。若两个格子有公共顶点,那么他们就是相邻的格子。(所以与 (i,j)(i,j) 相邻的格子有 $(i-1, j-1),(i-1 ,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)$)。

我们定义一个格子的集合 S\mathbf S 为山峰(山谷)当且仅当:

  • S\mathbf S 的所有格子都有相同的高度;
  • S\mathbf S 的所有格子都联通;
  • 对于 sSs\in \mathbf S,与 ss 相邻的 sSs'\notin \mathbf S。都有 w(s)>w(s)w(s) > w(s')(山峰),或者 w(s)<w(s)w(s) < w(s')(山谷)。

你的任务是,对于给定的地图,分别求出山峰和山谷的数量。

如果所有格子都有相同的高度,那么整个地图即是山峰,又是山谷

输入格式

第一行包含一个正整数 nn,表示地图的边长 (1n103)(1\leq n\leq 10^3)。接下来一个 n×nn\times n 的矩阵,表示地图上每个坐标的高度 ww (0w109)(0\leq w \leq 10^9)

输出格式

应包含两个数,分别表示山峰和山谷的数量。

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
2 1
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
3 3

数据规模与约定

1n103,0w(x,y)1091\leq n\leq 10^3,0\leq w(x,y)\leq 10^9

题目来源

[POI2007] 山峰和山谷Grz