#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