P2919 [USACO08NOV] Guarding the Farm S
题目描述
农场有许多小山丘,约翰农夫希望在这些小山丘上放置守卫,以确保他珍贵的奶牛的安全。
他想知道如果他希望在每个小山丘的顶部放置一个守卫,他需要多少守卫。他有一张地图,这张地图是一个整数矩阵;矩阵有 $N$ 行($1 < N \leq 700$)和 $M$ 列($1 < M \leq 700$)。矩阵中的每个元素表示一个高度 $H_{ij}$($0 \leq H_{ij} \leq 10,000$)。请帮助他确定地图上有多少个山顶。
一个山顶是由一个或多个相邻且具有相同值的矩阵元素组成,这些元素被地图的边缘或具有较低(较小)高度的元素完全包围。如果两个不同的元素的 $X$ 坐标差的绝对值不大于 1,且 $Y$ 坐标差的绝对值也不大于 1,则它们是相邻的。
输入格式
\* 第 1 行:两个用空格分隔的整数:$N$ 和 $M$
\* 第 2 行到第 $N+1$ 行:第 $i+1$ 行描述矩阵的第 $i$ 行,包含 $M$ 个用空格分隔的整数:$H_{ij}$
输出格式
\* 第 1 行:一个整数,表示山顶的数量
说明/提示
有三个山峰:左上角高度为 4 的一个,底部高度为 2 的一个点,以及右上角高度为 1 的一个点。
(由 ChatGPT 4o 翻译)