← 返回题目
题库练习 GRZ-Ridges and Valleys
← 上一题 下一题 →

A2459 | GRZ-Ridges and Valleys

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个地图，为小朋友想要旅行的区域，地图被分为n*n的网格，每个格子(i,j) 的高度 $w(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为山峰（山谷）当且仅当：

$1$. $S$的所有格子都有相同的高度。

$2$. $S$ 的所有格子都联通

$3$ .对于 $s$ 属于 $S$ ，与 $s$x相邻的s’不属于 $S$ 。都有 $ws > ws’$（山峰），或者$ws < ws’$（山谷） 。

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

输入格式

输入 第一行包含一个正整数n，表示地图的大小$（1<=n<=1000）$。接下来一个$n*n$ 的矩阵，表示地图上每个格子的高度。$(0<=w<=1000000000)$

输出格式

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

输入输出样例

输入 #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
C++ 编辑器
输入
输出