417.md

Pacific Atlantic Water Flow

Description

link

---

Solution

标准的DFS + Memory

分别遍历太平洋和大西洋的到达矩阵，当能够接通的时候便设置为true，最后合并判断即可

这里讲一下DFS的时间复杂度判断：如果是最坏情况的话，首先因为初始DFS的循环是O(M + N)，每个点的最大遍历长度是O(MN)，这就是最坏情况的时间复杂度

---

Code

最坏情况下的时间复杂度是O((M+N)*MN)，空间复杂度是O(MN)

class Solution:
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        if not matrix or not matrix[0]:
            return []
        m, n = len(matrix), len(matrix[0])
        
        Pacific = [[False] * n for _ in range(m)]
        Atlantic = [[False] * n for _ in range(m)]
        
        for i in range(m):
            self.dfs(Pacific, matrix, m, n, i, 0)
            self.dfs(Atlantic, matrix, m, n, i, n - 1)
        for j in range(n):
            self.dfs(Pacific, matrix, m, n, 0, j)
            self.dfs(Atlantic, matrix, m, n, m - 1, j)
        
        res = []
        for i in range(m):
            for j in range(n):
                if Pacific[i][j] and Atlantic[i][j]:
                    res.append([i, j])
        return res

    def dfs(self, visited, matrix, m, n, i, j):
        visited[i][j] = True
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        for h, v in directions:
            x, y = i + h, j + v
            if x < 0 or x >= m or y < 0 or y >= n or matrix[x][y] < matrix[i][j] or visited[x][y]:
                continue
            self.dfs(visited, matrix, m, n, x, y)