大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

上面一条边和左边一条边代表的是太平洋，右边一条边和下边一条边代表的是大西洋。

现在告诉你水往低处流，问哪些位置的水能同时流进太平洋和大西洋？

解题方法

要解决的问题：哪些位置的雨水能同时流进太平洋和大西洋。
重要思路：将水的流向反转，假设太平洋和大西洋的水 从低向高 “攀登”，分别能到达哪些位置，分别用 p_visited 和 a_visited 表示。两者的交集就代表能同时流向太平洋和大西洋的位置。

DFS

直接DFS求解。一般来说 DFS 需要有固定的起点，但是对于本题，4 条边都是能与大洋接壤的，那么就把 4 条边界的每个位置都算作 DFS 的起点。

使用两个二维数组 p_visited 和 a_visited，分别记录太平洋和大西洋的水能从低向高“攀登”到的位置。

然后对 4 条边进行遍历，看以这些边的每个位置为起点，进行攀登；把能到达的哪些的位置，分别在 p_visited 和 a_visited标记出来。

注意了，因为是从边界向中间去“攀登”，所以，这个时候是新的点要比当前的点海拔高才行。

Python代码如下：

  1. class Solution(object):
  2.     def pacificAtlantic(self, matrix):
  3.         """
  4.         :type matrix: List[List[int]]
  5.         :rtype: List[List[int]]
  6.         """
  7.         if not matrix or not matrix[0]: return []
  8.         m, n = len(matrix), len(matrix[0])
  9.         p_visited = [[False] * n for _ in range(m)]
  10.         a_visited = [[False] * n for _ in range(m)]
  11.         for i in range(m):
  12.             self.dfs(p_visited, matrix, m, n, i, 0)
  13.             self.dfs(a_visited, matrix, m, n, i, n -1)
  14.         for j in range(n):
  15.             self.dfs(p_visited, matrix, m, n, 0, j)
  16.             self.dfs(a_visited, matrix, m, n, m - 1, j)
  17.         res = []
  18.         for i in range(m):
  19.             for j in range(n):
  20.                 if p_visited[i][j] and a_visited[i][j]:
  21.                     res.append([i, j])
  22.         return res
  24.     def dfs(self, visited, matrix, m, n, i, j):
  25.         visited[i][j] = True
  26.         directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
  27.         for dire in directions:
  28.             x, y = i + dire[0], j + dire[1]
  29.             if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or matrix[x][y] < matrix[i][j]:
  30.                 continue
  31.             self.dfs(visited, matrix, m, n, x, y)

C++代码如下：

class Solution {
public:
    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        const int M = matrix.size();
        const int N = matrix[0].size();
        vector<vector<bool>> p_visited(M, vector<bool>(N));
        vector<vector<bool>> a_visited(M, vector<bool>(N));
        for (int i = 0; i < M; ++i) {
            dfs(matrix, p_visited, i, 0);
            dfs(matrix, a_visited, i, N - 1);
        }
        for (int j = 0; j < N; ++j) {
            dfs(matrix, p_visited, 0, j);
            dfs(matrix, a_visited, M - 1, j);
        }
        vector<pair<int, int>> res;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (p_visited[i][j] && a_visited[i][j]) {
                    res.push_back({i, j});
                }
            }
        }
        return res;
    }
    void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int i, int j) {
        const int M = matrix.size();
        const int N = matrix[0].size();
        visited[i][j] = true;
        vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (auto d : dirs) {
            int nx = i + d.first;
            int ny = j + d.second;
            if (nx >= 0 && nx < M && ny >= 0 && ny < N && !visited[nx][ny] && matrix[nx][ny] >= matrix[i][j]) {
                dfs(matrix, visited, nx, ny);
            }
        }
    }
};

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

参考资料：

https://leetcode.com/problems/pacific-atlantic-water-flow/discuss/90739/Python-DFS-bests-85.-Tips-for-all-DFS-in-matrix-question./181815

总结

  1. DFS 的变化。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。