logo AlgoBeat OnlineJudge
登录 注册

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

内存限制:162 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

给定一个地图,为 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

数据范围与提示

[POI2007] 山峰和山谷Grz