A91482.Welcome24ever 和山丘

普及+/提高

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

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

更具体地说:

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

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

输入格式

  • 11 行:两个用空格分隔的整数 NNMM
  • 22 行到第 N+1N+1 行:第 i+1i+1 行包含 MM 个整数,表示矩阵第 ii 行的高度值 Hi1,Hi2,,HiMH_{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

说明/提示

共有三座山顶:

  • 左上角那一块高度为 44 的连通块;
  • 底部中间高度为 22 的那一块;
  • 右上角高度为 11 的那一块。
首页