A91482.Welcome24ever 和山丘
普及+/提高
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
农场里有许多小山丘,Welcome24ever 希望在这些小山丘上放置守卫,以确保他珍贵的奶牛的安全。
他想知道,如果要在每一座小山丘的顶部放置一个守卫,一共需要多少个守卫。
他有一张地图,这张地图是一个整数矩阵,共有 N 行(1<N≤700)和 M 列(1<M≤700)。矩阵中的每个元素表示一个高度 Hij(0≤Hij≤10000)。请你帮他确定地图上有多少个“山顶”。
我们将山顶定义为:由一个或多个相邻且高度相同的格子组成的连通块,这个连通块被地图的边界或高度严格更低的格子完全包围。
更具体地说:
- 如果两个格子的行坐标之差的绝对值不超过 1,并且列坐标之差的绝对值也不超过 1,
那么这两个格子是相邻的(也就是八连通:上下左右加四个对角都算相邻); - 若若干个高度相同的格子构成一个在八连通意义下的连通块,并且:
- 对这个连通块中任意一个格子,八个方向上所有相邻的格子,要么在矩阵范围外(被边界挡住),要么高度小于该连通块的高度;
- 则这个连通块是一座“山顶”,需要放置一个守卫。
你的任务是:计算地图上一共有多少座这样的山顶。
输入格式
- 第 1 行:两个用空格分隔的整数 N 和 M。
- 第 2 行到第 N+1 行:第 i+1 行包含 M 个整数,表示矩阵第 i 行的高度值 Hi1,Hi2,…,HiM。
输出格式
- 输出一行,一个整数,表示山顶的数量。
输入输出样例
输入#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 的那一块。