P2919 [USACO08NOV]守护农场Guarding the Farm

    • 435通过
    • 1.2K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 搜索 概率论,统计 深度优先搜索,DFS USACO 2008 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    农夫John的农场里有很多小山丘,他想要在那里布置一些保镖去保卫他的那些相当值钱的奶牛们。

    他想知道如果在一座小山丘上布置一名保镖的话,他最少总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行(1<N≤700)和M列( 1<M≤ 700) 。矩阵中的每个元素都有一个值H_ij(0≤H_ij≤10000)来表示该地区的海拔高度。

    小山丘的定义是:若地图中一个元素所邻接的所有元素都比这个元素高度要小(或它邻接的是地图的边界),则该元素和其周围所有按照这样顺序排列的元素的集合称为一个小山丘。这里邻接的意义是:若一个位置的横纵坐标与另一个位置的横纵坐标相差不超过1,则称这两个元素邻接,比如某个非边界点的位置有8个相邻点:上、下、左、右、左上、右上、左下、右下。

    请你帮助他统计出地图上最少且尽量高的小山丘数量。

    题目描述

    The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows.

    He wonders how many guards he will need if he wishes to put one on top of each hill. He has a map supplied as a matrix of integers; the matrix has N (1 < N <= 700) rows and M (1 < M <= 700) columns. Each member of the matrix is an altitude H_ij (0 <= H_ij <= 10,000). Help him determine the number of hilltops on the map.

    A hilltop is one or more adjacent matrix elements of the same value surrounded exclusively by either the edge of the map or elements with a lower (smaller) altitude. Two different elements are adjacent if the magnitude of difference in their X coordinates is no greater than 1 and the magnitude of differences in their Y coordinates is also no greater than 1.

    输入输出格式

    输入格式:

    * Line 1: Two space-separated integers: N and M

    * Lines 2..N+1: Line i+1 describes row i of the matrix with M

    space-separated integers: H_ij

    输出格式:

    * Line 1: A single integer that specifies the number of hilltops

    输入输出样例

    输入样例#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 
    

    说明

    There are three peaks: The one with height 4 on the left top, one of the points with height 2 at the bottom part, and one of the points with height 1 on the right top corner.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。