太平洋大西洋水流问题为什么要反向 DFS/BFS？

简化版

这题不要从每个格子出发找两片海，复杂度太高。更好的做法是反向从太平洋边界和大西洋边界分别出发，只能从低处或等高处走到高处，分别标记能“反向到达”的格子，最后取两个标记集合的交集。

详细版

正向水流规则是从高处流向低处或等高处。反过来，从海边往内陆走时，只能走到高度大于等于当前高度的格子。分别以太平洋边界（上边、左边）和大西洋边界（下边、右边）作为多源起点，做 DFS/BFS 得到 pacificReach 和 atlanticReach。两个集合都为 true 的格子，就是水既能流到太平洋也能流到大西洋的位置。

复杂度是 O(mn)，因为每片海的反向遍历最多访问每个格子一次。相比从每个格子单独搜索两片海的 O((mn)^2) 最坏情况，反向多源搜索更适合面试。

完整版教学

一、为什么正向从每个格子搜会慢

如果从每个格子都做一次 DFS，判断能否流到太平洋和大西洋，最坏会重复搜索大量路径。一个 200 * 200 的矩阵有 40000 个格子，如果每个格子都可能搜索接近全图，复杂度会非常难看。

每个格子出发:
cell1 -> 搜一大片
cell2 -> 又搜一大片
...
cell40000 -> 继续重复

这题的目标不是求某一条路径，而是找所有能到两片海的格子。遇到“从所有点出发判断能否到某个边界”的题，要立刻想到反向从边界出发，把多次搜索合并成少数几次搜索。

二、水流规则反过来是什么

正向规则是：水可以从当前格子流到高度小于等于当前高度的邻居。反向从海边往内陆走时，方向相反，所以只能走到高度大于等于当前高度的邻居。

正向: high -> low
反向: ocean -> higher or equal cells

例如高度 5 的格子能正向流到高度 3 的邻居；反向搜索时，如果已经站在高度 3，就可以走回高度 5，表示 5 的水能流到这片海。这个反向条件是整题最关键的转化。

三、两片海的边界起点

太平洋接触矩阵的上边和左边，大西洋接触下边和右边。反向搜索时，这些边界格子天然可达对应海洋，所以它们是多源 DFS/BFS 的起点。

海洋	起点边界
太平洋	第 0 行、第 0 列
大西洋	最后一行、最后一列

用两个布尔矩阵分别记录可达性。最后扫描所有格子，如果 pacific[r][c] && atlantic[r][c]，就加入答案。

四、DFS 代码骨架

DFS 函数需要传入当前海洋对应的 visited 矩阵。进入一个格子后标记为 true，再尝试走向四邻域中高度不低于当前高度的格子。

void dfs(int[][] h, boolean[][] seen, int r, int c) {
    if (seen[r][c]) return;
    seen[r][c] = true;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nr >= h.length || nc < 0 || nc >= h[0].length) continue;
        if (h[nr][nc] >= h[r][c]) dfs(h, seen, nr, nc);
    }
}

初始化时，对太平洋的上边和左边调用 DFS；对大西洋的下边和右边调用 DFS。边角格子会被调用两次，但 seen 会挡住重复访问。

五、用数字矩阵理解交集

看一个小矩阵：

1 2 2
3 2 3
2 4 5

太平洋从上边、左边反向爬坡，大西洋从下边、右边反向爬坡。高度 4 和 5 在右下区域容易到大西洋，同时由于可以沿反向非降路径从太平洋边界到达部分高点，它们可能进入交集。最终答案不是“最高的点”，而是“两片海反向都能爬到的点”。

Pacific reach   ∩   Atlantic reach   =   answer cells

交集思想可以避免你在单个格子里写两个复杂的搜索函数，也更不容易超时。

六、BFS 版本和复杂度

BFS 也可以做，把每片海的所有边界格子先入队，然后按同样的反向条件扩散。BFS 的优点是避免递归栈，DFS 的优点是代码短。

方法	时间复杂度	空间复杂度	特点
DFS	O(mn)	O(mn)	代码短，注意递归深度
BFS	O(mn)	O(mn)	队列稳定，适合大矩阵

为什么是 O(mn)？每个海洋的 visited 矩阵最多把每个格子标记一次，两片海就是 2mn，常数省略后仍是 O(mn)。

七、常见误区与追问

记忆钩子：不要问“每滴水能流到哪”，要问“海水反向能爬到哪”；两片海都能反向爬到的格子就是答案。

• 误区：从每个格子出发搜两片海。 这样会重复搜索，最坏复杂度很高；反向多源搜索只遍历两遍矩阵。
• 误区：反向条件写成 <=。 反向从海往内陆走，应走到高度大于等于当前高度的格子。
• 误区：只把四个角作为起点。 海洋接触整条边界，上边和左边都属于太平洋，下边和右边都属于大西洋。
• 追问：为什么答案取交集？ 一个格子被太平洋反向到达，表示它能正向流到太平洋；被大西洋反向到达同理，两者同时满足就是结果。
• 追问：能不能原地标记？ 可以用 bit 标记或整数状态优化，但两个 boolean 矩阵更清晰。
• 追问：递归太深怎么办？ 用 BFS 队列替代 DFS，访问规则不变。

八、加强记忆

这题的核心是反向多源搜索。正向是高流低，反向就是从海边向高度不低于当前格子的邻居扩散。分别得到太平洋可达集合和大西洋可达集合，最后取交集。它考的不是复杂图论，而是能否把“每点到边界”的重复搜索改成“边界到所有点”的一次性标记。