太平洋大西洋水流问题
矩阵找能流到太平洋与大西洋的格子。
矩阵找能流到太平洋与大西洋的格子。
当前节点的合法邻居是谁，访问标记何时写入？
从两大洋边界 DFS 反向标记可达,交集即答案。
先说结论：这道题到底解决什么
怎样从“矩阵找能流到太平洋与大西洋的格子。”推导出 网格 DFS · 双源，并证明每次状态变化都不会漏掉答案？
中心结论：从两大洋边界 DFS 反向标记可达,交集即答案。
- 1.暴力方案在哪里重复计算，为什么仍然是正确基线？
- 2.当前节点的合法邻居是谁，访问标记何时写入？
- 3.不变量“反向沿高度不降 DFS。”为什么能保证算法安全前进？
完整题目与题意拆解
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
在本站主例中，矩阵找能流到太平洋与大西洋的格子。
算法最终需要得到或观察：边界交集格子列表。
- • 输入：矩阵找能流到太平洋与大西洋的格子。
- • 机器需要维护：pac/atl 可达集合。
- • 最终可观察结果：边界交集格子列表。
先看清算法到底要维护什么
先建立输入、目标、输出和第一批状态，不急着进入模板。
能流到太平洋/大西洋的格子分别标记
第一层方案：暴力做法
重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。
重复工作究竟发生在哪里
把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。
能流到太平洋/大西洋的格子分别标记
整体地图：先做什么，再做什么
- 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
- 2状态只维护 pac/atl 可达集合。
- 3转移每一步按照 从两大洋边界 DFS 反向标记可达,交集即答案。
- 4收尾读取 边界交集格子列表。，并复核边界与复杂度。
图搜索前线：核心概念
先把题目对象翻译成节点和边，再选择 BFS 或 DFS。
这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：pac/atl 可达集合。
- • 反向沿高度不降 DFS。
建立“图搜索前线”心智模型
用主例建立核心状态，先预测下一步，再公开正确分支和理由。
能流到太平洋/大西洋的格子分别标记
核心机制：状态如何一步步变化
暴力解法，利用 DFS 把二维数据按照行优先搜索一遍，分别标记出太平洋和大西洋水流能到达的位置。再按照列优先搜索一遍，标记出太平洋和大西洋水流能到达的位置。最后两者都能到达的坐标即为所求。
从两大洋边界 DFS 反向标记可达,交集即答案。
执行过程中持续维护：pac/atl 可达集合。
正确性依赖以下不变量：反向沿高度不降 DFS。
面试时可以压缩为：两趟边界 DFS+交集 O(mn)。
落到当前题，执行机制可以压缩为：从两大洋边界 DFS 反向标记可达,交集即答案。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。
一次状态转移为什么成立
集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。
太平洋侧 13 格
正确性证明：为什么不会漏答案
初始化：算法开始时，全部合法候选仍在状态表示范围内；反向沿高度不降 DFS。
保持：执行“从两大洋边界 DFS 反向标记可达,交集即答案。”时，只删除已经能证明不可能的候选，并把新信息写回 pac/atl 可达集合。
终止：没有待处理状态或达到命中条件时，当前可观察结果就是“边界交集格子列表。”。
完整执行过程
- 1题目与输入矩阵找能流到太平洋与大西洋的格子。 因为：从两大洋边界 DFS 反向标记可达,交集即答案。
- 2从两大洋边界反向 DFS从边界向内,高度非递减。 因为：反向流等价于正向可达。
- 3太平洋可达集完成上边界+左边界 DFS。 因为：反向沿高度非递减。
- 413 格可同时流向两大洋两大集合求交。 因为：O(mn) 双 DFS。
- 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
- 6收尾与复杂度边界交集格子列表。 因为：时间 O(n) · 空间 O(1)。从两大洋边界 DFS 反向标记可达,交集即答案。
从输入完整走到可观察结果
从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。
能流到太平洋/大西洋的格子分别标记
把动画和 Go 代码逐行对应
代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。
让每个动作都落到 Go 分支
重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。
能流到太平洋/大西洋的格子分别标记
完整 Go 提交代码与最小测试
import "math"
func pacificAtlantic(matrix [][]int) [][]int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return nil
}
row, col, res := len(matrix), len(matrix[0]), make([][]int, 0)
pacific, atlantic := make([][]bool, row), make([][]bool, row)
for i := 0; i < row; i++ {
pacific[i] = make([]bool, col)
atlantic[i] = make([]bool, col)
}
for i := 0; i < row; i++ {
dfs(matrix, i, 0, &pacific, math.MinInt32)
dfs(matrix, i, col-1, &atlantic, math.MinInt32)
}
for j := 0; j < col; j++ {
dfs(matrix, 0, j, &pacific, math.MinInt32)
dfs(matrix, row-1, j, &atlantic, math.MinInt32)
}
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if atlantic[i][j] && pacific[i][j] {
res = append(res, []int{i, j})
}
}
}
return res
}
func dfs(matrix [][]int, row, col int, visited *[][]bool, height int) {
if row < 0 || row >= len(matrix) || col < 0 || col >= len(matrix[0]) {
return
}
if (*visited)[row][col] || matrix[row][col] < height {
return
}
(*visited)[row][col] = true
dfs(matrix, row+1, col, visited, matrix[row][col])
dfs(matrix, row-1, col, visited, matrix[row][col])
dfs(matrix, row, col+1, visited, matrix[row][col])
dfs(matrix, row, col-1, visited, matrix[row][col])
}func main() {
// 1. 主例
// 输入：mode="pacific-atlantic", grid=[["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"]]
// 期望：边界交集格子列表。
//
// 2. 失败 / 未命中
// 检查：正向从每格 DFS 会重复。
//
// 3. 边界
// 空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
//
// 4. 迁移
// LC200 岛屿；LC130 被围
}Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。
正确性与复杂度
执行过程中只保留仍可能影响答案的状态。从两大洋边界 DFS 反向标记可达,交集即答案。
额外状态主要用于维护：pac/atl 可达集合。
- • 反向沿高度不降 DFS。
最容易写错的地方
正向从每格 DFS 会重复。
必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。
最后复盘：带走逻辑链
- 1题意矩阵找能流到太平洋与大西洋的格子。
- 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
- 3优化从两大洋边界 DFS 反向标记可达,交集即答案。
- 4证明反向沿高度不降 DFS。
- 5复杂度时间 O(n)，空间 O(1)
- • LC200 岛屿
- • LC130 被围