A8053.水流问题
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
有一个 m×n 的矩形岛屿,与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界,而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m×n 的整数矩阵 heights,heights[r][c] 表示坐标 (r,c) 上单元格高于海平面的高度 。
岛上雨水较多,如果相邻单元格的高度小于或等于当前单元格的高度,雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
求出既可流向太平洋也可流向大西洋的单元格数目。
输入格式
第一行两个整数 n,m(1≤n,m≤1000),表示行数和列数。
接下来 n 行,每行 m 个整数。这些整数的值范围为 0∼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