#GT007. 太平洋大西洋水流问题

太平洋大西洋水流问题

说明

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

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

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

找到所有 既可流向太平洋也可流向大西洋  的格子,按行输出它们的下标。

如下图所示:

标黄的格子即为满足条件的格子。

输入格式

第一行两个整数 n 和 m

接下来是一个 n x m 的整数矩阵 heights

输出格式

每行两个整数 r c

按照 r c 从小到大顺序输出

样例

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 

提示

数据范围:
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 105