山峰和山谷
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
译自 POI 2007 Stage 2. Day 0「Ridges and Valleys」
给定一个 的网格状地图，每个方格 有一个高度 。如果两个方格有公共顶点，则它们是相邻的。
定义山峰和山谷如下：
- 均由地图上的一个连通块组成；
- 所有方格高度都相同；
- 周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。
求地图内山峰和山谷的数量。特别地，如果整个地图方格的高度均相同，则整个地图既是一个山谷，也是一个山峰。
输入格式
第一行一个整数 ，表示地图的大小。
接下来 行，每行 个整数表示地图。第 行有 个整数 $w_{i1}, w_{i2}, \ldots, w_{in} (0 \le w_{ij} \le 1\ 000\ 000\ 000)$，表示地图第 行格子的高度。
输出格式
输出一行两个整数，分别表示山峰和山谷的数量。
样例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
2 1
样例说明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
3 3
样例说明2
数据范围
C23暑假作业3-搜索-基础题
- Status
- Done
- Problem
- 20
- Open Since
- 2024-7-5 0:00
- Deadline
- 2024-10-27 23:59
- Extension
- 24 hour(s)