测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A6280. Welcome24ever 和山丘

编程题 普及+/提高
知识点

题目描述

农场里有许多小山丘,Welcome24ever 希望在这些小山丘上放置守卫,以确保他珍贵的奶牛的安全。

他想知道,如果要在每一座小山丘的顶部放置一个守卫,一共需要多少个守卫。
他有一张地图,这张地图是一个整数矩阵,共有 $N$ 行($1 < N \le 700$)和 $M$ 列($1 < M \le 700$)。矩阵中的每个元素表示一个高度 $H_{ij}$($0 \le H_{ij} \le 10\,000$)。请你帮他确定地图上有多少个“山顶”。

我们将**山顶**定义为:由一个或多个相邻且高度相同的格子组成的连通块,这个连通块被地图的边界或高度**严格更低**的格子完全包围。

更具体地说:

- 如果两个格子的行坐标之差的绝对值不超过 $1$,并且列坐标之差的绝对值也不超过 $1$,
那么这两个格子是**相邻**的(也就是八连通:上下左右加四个对角都算相邻);
- 若若干个高度相同的格子构成一个在八连通意义下的连通块,并且:
- 对这个连通块中任意一个格子,八个方向上所有相邻的格子,要么在矩阵范围外(被边界挡住),要么高度小于该连通块的高度;
- 则这个连通块是一座“山顶”,需要放置一个守卫。

你的任务是:计算地图上一共有多少座这样的山顶。

输入格式

- 第 $1$ 行:两个用空格分隔的整数 $N$ 和 $M$。
- 第 $2$ 行到第 $N+1$ 行:第 $i+1$ 行包含 $M$ 个整数,表示矩阵第 $i$ 行的高度值 $H_{i1}, H_{i2}, \dots, H_{iM}$。

输出格式

- 输出一行,一个整数,表示山顶的数量。

输入输出样例

输入 #1
8 7 
4 3 2 2 1 0 1 
3 3 3 2 1 0 1 
2 2 2 2 1 0 0 
2 1 1 1 1 0 0 
1 1 0 0 0 1 0 
0 0 0 1 1 1 0 
0 1 2 2 1 1 0 
0 1 1 1 2 1 0
输出 #1
3

说明/提示

共有三座山顶:

- 左上角那一块高度为 $4$ 的连通块;
- 底部中间高度为 $2$ 的那一块;
- 右上角高度为 $1$ 的那一块。
上一题 去做题 下一题