1332 - 太平洋大西洋的流水

通过次数

12

提交次数

25

时间限制 : 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列表依次记录上述位置的下标并输出。