- Pacific Atlantic Water Flow
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Example 1:
图片: https://uploader.shimo.im/f/ok4Y9wvZBhw1CNU8.jpg!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJleHAiOjE3MzE0MTQ2MjMsImZpbGVHVUlEIjoiZ08zb2RQWURiTHNqVjlxRCIsImlhdCI6MTczMTQxNDMyMywiaXNzIjoidXBsb2FkZXJfYWNjZXNzX3Jlc291cmNlIiwidXNlcklkIjo3MzYwMzI4MH0.eauLY9d9Jd_I3yZ-93kZZK0TsOfxw4K7_OWI9r7YELY
Input: heights = [[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]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
[0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
[1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
[1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
[2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
[3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
[3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
分析：
首先拿到这道题很明显能够判断出是一个二维平面回溯算法的题目，所以首先我们要准备一个移动坐标：
分别表示上右下左
self.directs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
一个判定是否在范围内的函数：
def in_area(self, x, y):
return 0 <= x < self.m and 0 <= y < self.n
然后继续分析，这道题是要寻找一个坐标既能够到达太平洋也能到达大西洋，但是这个过程一般不是一次深度搜索就能够完成的，所以我们从各边界开始逆流进行搜索。然后用两个二维数组进行记录，相当于进行了 4 次深度搜索，具体答案可以参考以下代码。
代码：
class Solution:
def init(self):
self.result_all = None
# 分别表示上右下左
self.directs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
self.m = 0
self.n = 0
# 表示能流到太平洋
self.po = None
# 表示能流到大西洋
self.ao = None
self.visited = None
def pacificAtlantic(self, matrix) :# 初始化一些东西self.result_all = []self.m = len(matrix)if self.m == 0:return self.result_allself.n = len(matrix[0])self.ao = [[0] * self.n for _ in range(self.m)]self.po = [[0] * self.n for _ in range(self.m)]self.visited = [[0] * self.n for _ in range(self.m)]# 本题顺着流不太好做，我们用逆流的方式来思考# 从上面的太平洋逆流for i in range(0, 1):for j in range(self.n):self.dfs(matrix, i, j, True)# 从左边的太平洋逆流self.visited = [[0] * self.n for _ in range(self.m)]for i in range(self.m):for j in range(0, 1):self.dfs(matrix, i, j, True)# 下面的大西洋self.visited = [[0] * self.n for _ in range(self.m)]for i in range(self.m - 1, self.m):for j in range(self.n):self.dfs(matrix, i, j, False)# 右边的大西洋self.visited = [[0] * self.n for _ in range(self.m)]for i in range(self.m):for j in range(self.n -1, self.n):self.dfs(matrix, i, j, False)for i in range(self.m):for j in range(self.n):if self.po[i][j] == 1 and self.ao[i][j] == 1:self.result_all.append((i, j))return self.result_alldef dfs(self, matrix, x, y, flag):if self.visited[x][y] == 1:returnself.visited[x][y] = 1if flag:# 表示是太平洋self.po[x][y] = 1else:# 表示是大西洋self.ao[x][y] = 1for i in range(4):newx = x + self.directs[i][0]newy = y + self.directs[i][1]if not self.in_area(newx, newy):continueif matrix[x][y] > matrix[newx][newy]:continueself.dfs(matrix, newx, newy, flag)returndef in_area(self, x, y):return 0 <= x < self.m and 0 <= y < self.n
