A8053.水流问题

普及/提高-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

有一个 m×nm \times n 的矩形岛屿,与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界,而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m×nm \times n 的整数矩阵 heightsheightsheights[r][c]heights[r][c] 表示坐标 (r,c)(r, c) 上单元格高于海平面的高度 。

岛上雨水较多,如果相邻单元格的高度小于或等于当前单元格的高度,雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

求出既可流向太平洋也可流向大西洋的单元格数目。

输入格式

第一行两个整数 n,m(1n,m1000)n,m(1 \leq n,m \leq 1000),表示行数和列数。

接下来 nn 行,每行 mm 个整数。这些整数的值范围为 01e50 \sim 1e5

输出格式

输出既可流向太平洋也可流向大西洋的单元格数目。

输入输出样例

  • 输入#1

    5 5
    1 2 2 3 5
    3 2 3 4 4
    2 4 5 3 1
    6 7 1 4 5
    5 1 1 2 4

    输出#1

    7
  • 输入#2

    2 2
    2 1
    1 2

    输出#2

    4

说明/提示

样例一解释:

【普及组算法9】广度优先搜索

0/20
首页