1332 - 太平洋大西洋的流水
时间限制 : 1 秒
内存限制 : 512 MB
输入整数m、n(1 ≤ m,n ≤ 200),再输入一个大小为 m × n的二维数组 ,表示有一个 m × n 的矩形岛屿heights,与太平洋和大西洋相邻。“太平洋”处于大陆的左边界和上边界,而“大西洋”处于大陆的右边界和下边界。
heights[r][c]表示坐标(r, c)上单元格高于海平面的高度 (0 <= heights[r][c] <= 105)。岛上雨水较多,如果相邻单元格的高度小于或等于当前单元格的高度,雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
输出网格坐标result的二维列表 ,其中 result[i] = [ri, ci] 表示雨水从单元格(ri, ci)流动既可流向太平洋也可流向大西洋。
输入
第一行输入正整数m和n。
接下来的m行,每行输入由0或1组成的n个数,表示矩陆地距离海平面的高度。
数据范围
对于30%的数据1<=m,n, heights[r][c]<=20;
对于30%的数据20<=m,n<=100,20< heights[r][c]<=50;
对于40%的数据100<=m,n<=200, heights[r][c] <= 105;
输出
输出二维列表,表示既可流向太平洋也可流向大西洋的坐标。
样例
输入
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
输出
0 4 1 3 1 4 2 2 3 0 3 1 4 0
提示
样例解释:
上图粉色的位置可以既可流向太平洋也可流向大西洋,故 result列表依次记录上述位置的下标并输出。