A6280 | Welcome24ever 和山丘
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
农场里有许多小山丘,Welcome24ever 希望在这些小山丘上放置守卫,以确保他珍贵的奶牛的安全。
他想知道,如果要在每一座小山丘的顶部放置一个守卫,一共需要多少个守卫。
他有一张地图,这张地图是一个整数矩阵,共有 $N$ 行($1 < N \le 700$)和 $M$ 列($1 < M \le 700$)。矩阵中的每个元素表示一个高度 $H_{ij}$($0 \le H_{ij} \le 10\,000$)。请你帮他确定地图上有多少个“山顶”。
我们将**山顶**定义为:由一个或多个相邻且高度相同的格子组成的连通块,这个连通块被地图的边界或高度**严格更低**的格子完全包围。
更具体地说:
- 如果两个格子的行坐标之差的绝对值不超过 $1$,并且列坐标之差的绝对值也不超过 $1$,
那么这两个格子是**相邻**的(也就是八连通:上下左右加四个对角都算相邻);
- 若若干个高度相同的格子构成一个在八连通意义下的连通块,并且:
- 对这个连通块中任意一个格子,八个方向上所有相邻的格子,要么在矩阵范围外(被边界挡住),要么高度小于该连通块的高度;
- 则这个连通块是一座“山顶”,需要放置一个守卫。
你的任务是:计算地图上一共有多少座这样的山顶。
他想知道,如果要在每一座小山丘的顶部放置一个守卫,一共需要多少个守卫。
他有一张地图,这张地图是一个整数矩阵,共有 $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}$。
- 第 $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$ 的那一块。
- 左上角那一块高度为 $4$ 的连通块;
- 底部中间高度为 $2$ 的那一块;
- 右上角高度为 $1$ 的那一块。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?