TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1528
  • 题目
  • P1528【Usaco Dec08 Brone】劣质的草
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    贝茜像其它奶牛一样正在吃草,她正在思考她所在的地方。她注意到她只得到了一个平于海平面的广泛大片牧场。只有海拔1米或者更高更硬的草不那么美味。草随着海拔的增加越发难吃。 继续咀嚼,她意识到,这没有食欲的食物长成两侧的丘陵,形成了青翠美味丰富草地海洋中的一系列劣质草小岛 。贝茜穿上她的实验服,决心测定她的牧场有多少劣草小岛。她画出一张画有被分成R (1 < R <= 1,000) 行、C (1 < C<= 1,000)列的1米x1米小格子的地图。她为每个小格子测量了海拔高度,并四舍五入到非负整数。她饥饿地把所有美味草标的海拔标记成0。 她着手统计小岛。任何水平、垂直、斜向相邻的两个有劣草的格子将被认为在同一个岛中。在每一张她提供的地图中有多少劣草岛屿呢?

    输入格式
    • 行 1: 两个用空格隔开的整数: R 和 C
      * 行 2..R+1: 行 i+1 用C个看空格隔开的整数表示地图中的i行
    输出格式
    • 行 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

    样例输出

    2

    提示

    输出说明:
    有两个岛。最大的一个在左侧通过一个对角线延伸到最底层,
    最小的一个在右上角。