← 返回题目
题库练习 水流问题
← 上一题 下一题 →

A1744 | 水流问题

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

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

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

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

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

输入格式

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

接下来 $n$ 行，每行 $m$ 个整数。这些整数的值范围为 $0 \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
C++ 编辑器
输入
输出