6036: 【系列题】图论(七)太平洋大西洋水流问题

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:3 Solved:2

Description

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

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

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

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

如下图所示:

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

Input

第一行两个整数 n 和 m

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

Output

每行两个整数 r c

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

Sample Input Copy

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

Sample Output Copy

0 4 
1 3 
1 4 
2 2 
3 0 
3 1 
4 0 

HINT

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