「翻译」P2919 [USACO08NOV] Guarding the Farm S

xzlhxc · 2022-10-26 16:45:59 · 个人记录

P2919 [USACO08NOV] 保卫S农场

农夫 John 的农场里有很多个山丘，他想要安排一些保镖在每个山丘上去保护他的那些值钱的奶牛们。

他有一张地形图，用一个 N 行 M 列的数字矩阵表示。矩阵中的每个元素 H_{ij} 为一个整数，表示该点的海拔高度。

山丘的定义：对于地形图中的一个元素或者若干个相邻且海拔相等的元素，若除了它（们）之外的，与它（们）相邻的所有元素的海拔高度都小于它（们），就称这个元素或者这些元素组成的集合为一个山丘。

相邻的定义：对于两个元素，若它们的行数之差与列数之差都不超过 1，则称这两个元素相邻（换言之，这里的相邻是八连通的。）如下，所有的 1 与 0 相邻。

1 1 1
1 0 1
1 1 1

他想知道，如果在每个山丘上都安排一名保镖，他需要多少名保镖。

共 N+1 行。

第 1 行：两个整数 N,M,用空格隔开。第 2\sim N+1 行：M 个整数，用空格隔开，第 i 行第 j 个数表示 H_{ij}。

共 1 行 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

共有 3 个山丘，分别在左上角（只有单个元素，海拔为 4），右上角（有 2 个元素，海拔为 1 ），中间最下面（有 3 个元素，海拔为 2）。