一、问题描述
给定一个 m x n 的非负整数矩阵 heights ，矩阵的左边界和上边界毗邻太平洋，右边界和下边界毗邻大西洋。水流的流动规则为：只能从高处流向低处，或者在同等高度的单元格之间流动。请找出矩阵中所有既可以流向太平洋，又可以流向大西洋的单元格坐标。
示例输入：
cpp
heights = [
[1,2,2,3,5],
[3,2,3,4,4],
[2,4,5,3,1],
[6,5,4,3,2],
[1,3,1,5,3]
]
示例输出： [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,3],[4,4]]
输出解释：例如单元格 (0,4) 高度为5，既能向上/向左流向太平洋，也能向下流向大西洋；单元格 (3,0) 高度为6，是左边界（太平洋）单元格，同时可向下/向右流动最终抵达大西洋。
二、核心思路：逆向搜索（解题关键）
如果直接从矩阵中的每个单元格出发，分别搜索是否能到达太平洋和大西洋，会存在大量重复计算，时间复杂度较高（最坏情况下为 O((m*n)^2)）。因此，我们需要采用逆向思考的优化策略，大幅降低时间成本。
逆向搜索的逻辑推导
1. 正向流动：单元格 → 海洋，要求路径上的单元格高度非递增；
2. 逆向流动：海洋 → 单元格，要求路径上的单元格高度非递减（因为逆向流动等价于正向流动的逆过程）；
3. 标记可达性：
从太平洋的所有边界单元格（左边界 y=0 、上边界 x=0 ）出发，按照逆向流动规则，标记所有能被太平洋“覆盖”的单元格；
从大西洋的所有边界单元格（右边界 y=n-1 、下边界 x=m-1 ）出发，按照逆向流动规则，标记所有能被大西洋“覆盖”的单元格；
4. 求交集：同时被太平洋和大西洋标记的单元格，就是既可以流向太平洋，又可以流向大西洋的目标单元格。
方向数组定义
为了简化四个方向（上、下、左、右）的遍历代码，我们定义一个方向数组：
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
其中 {-1,0} 代表向上移动， {1,0} 代表向下移动， {0,-1} 代表向左移动， {0,1} 代表向右移动。
三、三种解法实现（C++版本）
方法1：DFS递归实现
完整代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
private:
// 定义四个移动方向：上、下、左、右
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int m, n; // 矩阵的行数和列数
/**
* @brief DFS递归函数：标记能被指定海洋逆向覆盖的单元格
* @param heights 输入的高度矩阵
* @param visited 标记矩阵，visited[x][y]=true表示该单元格可流向对应海洋
* @param x 当前单元格的行坐标
* @param y 当前单元格的列坐标
*/
void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {
// 1. 标记当前单元格为已访问，避免重复搜索
visited[x][y] = true;
// 2. 遍历四个方向的邻接单元格
for (auto& dir : dirs) {
// 计算邻接单元格的坐标
int nx = x + dir[0];
int ny = y + dir[1];
// 3. 邻接单元格的合法性判断（四要素缺一不可）
// - 行坐标nx在[0, m-1]范围内
// - 列坐标ny在[0, n-1]范围内
// - 该单元格未被访问过（避免重复标记）
// - 邻接单元格高度 >= 当前单元格高度（满足逆向流动规则）
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && heights[nx][ny] >= heights[x][y]) {
// 递归搜索邻接单元格
dfs(heights, visited, nx, ny);
}
}
}
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
vector<vector<int>> res; // 存储最终结果的二维数组
// 边界条件：如果矩阵为空，直接返回空结果
if (heights.empty() || heights[0].empty()) return res;
// 初始化矩阵的行数和列数
m = heights.size();
n = heights[0].size();
// 定义两个标记矩阵：分别记录可流向太平洋、大西洋的单元格
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
// 1. 从边界单元格出发，启动DFS标记
// 遍历左边界（y=0，太平洋）和右边界（y=n-1，大西洋）的所有单元格
for (int i = 0; i < m; i++) {
dfs(heights, pacific, i, 0); // 左边界单元格(i,0)启动太平洋的DFS
dfs(heights, atlantic, i, n-1); // 右边界单元格(i,n-1)启动大西洋的DFS
}
// 遍历上边界（x=0，太平洋）和下边界（x=m-1，大西洋）的所有单元格
for (int j = 0; j < n; j++) {
dfs(heights, pacific, 0, j); // 上边界单元格(0,j)启动太平洋的DFS
dfs(heights, atlantic, m-1, j); // 下边界单元格(m-1,j)启动大西洋的DFS
}
// 2. 遍历两个标记矩阵，收集交集单元格
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 同时被太平洋和大西洋标记的单元格，即为目标单元格
if (pacific[i][j] && atlantic[i][j]) {
res.push_back({i, j});
}
}
}
// 返回最终结果
return res;
}
};
// 测试函数：验证代码正确性
int main() {
vector<vector<int>> heights = {
{1,2,2,3,5},
{3,2,3,4,4},
{2,4,5,3,1},
{6,5,4,3,2},
{1,3,1,5,3}
};
Solution s;
vector<vector<int>> res = s.pacificAtlantic(heights);
// 打印结果
cout << "符合条件的单元格坐标：" << endl;
for (auto& pos : res) {
cout << "[" << pos[0] << "," << pos[1] << "] ";
}
cout << endl;
return 0;
}
代码执行步骤拆解
1. 初始化：判断矩阵是否为空，获取矩阵的行数 m 和列数 n ，创建两个标记矩阵 pacific 和 atlantic 。
2. 边界DFS启动：分别从太平洋和大西洋的四个边界单元格出发，调用DFS函数标记可达单元格。
3. 结果收集：遍历所有单元格，将同时被两个标记矩阵标记的单元格坐标存入结果数组。
4. 返回结果：输出最终的目标单元格坐标。
递归DFS的优缺点
优点：代码结构清晰，逻辑直观，无需手动维护栈结构，开发效率高。
缺点：当矩阵规模极大时，函数调用栈的深度会超出系统限制，导致栈溢出错误。
方法2：DFS栈实现（非递归）
为了解决递归DFS的栈溢出问题，我们可以采用手动栈来模拟函数调用栈的行为，实现非递归版本的DFS。这种方式完全由开发者控制栈的大小，稳定性更高。
完整代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Solution {
private:
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int m, n;
/**
* @brief 非递归DFS函数：用手动栈实现，标记可流向对应海洋的单元格
* @param heights 高度矩阵
* @param visited 标记矩阵
* @param x 起始单元格行坐标
* @param y 起始单元格列坐标
*/
void dfs_stack(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {
// 定义栈，存储待处理的单元格坐标，使用pair<int, int>类型
stack<pair<int, int>> st;
// 1. 将起始单元格入栈，并标记为已访问
st.push({x, y});
visited[x][y] = true;
// 2. 栈不为空时，循环处理
while (!st.empty()) {
// 取出栈顶单元格（不立即弹出，先处理其邻接单元格）
auto [cur_x, cur_y] = st.top();
st.pop(); // 弹出栈顶元素，开始处理
// 遍历四个方向的邻接单元格
for (auto& dir : dirs) {
int nx = cur_x + dir[0];
int ny = cur_y + dir[1];
// 合法性判断：边界+未访问+高度非递减
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && heights[nx][ny] >= heights[cur_x][cur_y]) {
// 标记为已访问，并压入栈中等待处理
visited[nx][ny] = true;
st.push({nx, ny});
}
}
}
}
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
vector<vector<int>> res;
if (heights.empty() || heights[0].empty()) return res;
m = heights.size();
n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
// 边界启动非递归DFS
for (int i = 0; i < m; i++) {
dfs_stack(heights, pacific, i, 0);
dfs_stack(heights, atlantic, i, n-1);
}
for (int j = 0; j < n; j++) {
dfs_stack(heights, pacific, 0, j);
dfs_stack(heights, atlantic, m-1, j);
}
// 收集交集结果
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
res.push_back({i, j});
}
}
}
return res;
}
};
// 测试代码同方法1
非递归DFS的核心逻辑
1. 栈初始化：将起始单元格压入栈，并标记为已访问，避免重复入栈。
2. 循环处理栈元素：当栈不为空时，弹出栈顶单元格，遍历其四个方向的邻接单元格。
3. 邻接单元格处理：对符合条件的邻接单元格，标记为已访问并压入栈，等待后续处理。
非递归DFS的优缺点
优点：避免了函数调用栈溢出的问题，稳定性强，适用于大规模矩阵。
缺点：需要手动管理栈结构，代码比递归版本稍显繁琐。
方法3：BFS实现（队列）
广度优先搜索（BFS）是另一种经典的搜索算法，它采用队列作为核心数据结构，按照层序遍历的顺序处理单元格，即先处理当前单元格的所有邻接单元格，再处理邻接单元格的邻接单元格。
在太平洋大西洋水流问题中，BFS的核心逻辑与DFS一致，区别仅在于数据结构的选择和遍历顺序的不同。
完整代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
private:
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int m, n;
/**
* @brief BFS函数：用队列实现层序遍历，标记可流向对应海洋的单元格
* @param heights 高度矩阵
* @param visited 标记矩阵
* @param x 起始单元格行坐标
* @param y 起始单元格列坐标
*/
void bfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {
// 定义队列，存储待处理的单元格坐标
queue<pair<int, int>> q;
// 1. 起始单元格入队，并标记为已访问
q.push({x, y});
visited[x][y] = true;
// 2. 队列不为空时，循环处理
while (!q.empty()) {
// 取出队首单元格（队首元素是当前层的第一个单元格）
auto [cur_x, cur_y] = q.front();
q.pop(); // 弹出队首元素
// 遍历四个方向的邻接单元格
for (auto& dir : dirs) {
int nx = cur_x + dir[0];
int ny = cur_y + dir[1];
// 合法性判断
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && heights[nx][ny] >= heights[cur_x][cur_y]) {
visited[nx][ny] = true;
q.push({nx, ny}); // 符合条件的邻接单元格入队
}
}
}
}
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
vector<vector<int>> res;
if (heights.empty() || heights[0].empty()) return res;
m = heights.size();
n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false));
vector<vector<bool>> atlantic(m, vector<bool>(n, false));
// 边界启动BFS
for (int i = 0; i < m; i++) {
bfs(heights, pacific, i, 0);
bfs(heights, atlantic, i, n-1);
}
for (int j = 0; j < n; j++) {
bfs(heights, pacific, 0, j);
bfs(heights, atlantic, m-1, j);
}
// 收集结果
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j]) {
res.push_back({i, j});
}
}
}
return res;
}
};
// 测试代码同方法1
BFS的核心逻辑
1. 队列初始化：将起始单元格入队，并标记为已访问。
2. 层序处理：当队列不为空时，取出队首单元格，遍历其四个方向的邻接单元格。
3. 邻接单元格入队：对符合条件的邻接单元格，标记为已访问并压入队列，等待下一层处理。
BFS的适用场景
BFS的层序遍历特性使其更适合解决最短路径类问题，例如在无权图中寻找两点之间的最短距离。在本题中，BFS的时间复杂度和空间复杂度与DFS完全一致，仅遍历顺序不同。
四、三种方法的深度对比
| 方法 | 核心数据结构 | 遍历顺序 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
| DFS递归 | 函数调用栈 | 深度优先，先探入一条路径的尽头，再回溯处理其他路径 | O（mn） | O（mn） | 代码简洁、易理解、开发效率高 | 大规模矩阵易触发栈溢出 |
| DFS栈 | 手动栈 | 深度优先，与递归版遍历顺序一致 | O（mn） | O（mn） | 稳定性强，无栈溢出风险 | 代码稍繁琐，需手动管理栈 |
| BFS | 队列 | 广度优先，先处理当前单元格的所有邻接单元格，再处理下一层 | O （mn） | O（mn） | 层序遍历，适合最短路径问题 | 代码稍繁琐，需手动管理队列 |
核心结论：三种方法的时间复杂度和空间复杂度完全相同，区别仅在于遍历顺序和数据结构的选择。在实际开发中，可根据场景需求灵活选择：
小规模矩阵：优先选择DFS递归，开发效率更高；
规模矩阵：优先选择DFS栈或BFS，稳定性更强；
最短路径类问题：优先选择BFS。
五、总结与拓展
解题核心要点
1. 逆向思维是解决本题的关键，将“从单元格流向海洋”转化为“从海洋流向单元格”，大幅降低时间复杂度；
2. 方向数组是矩阵遍历问题的常用工具，能简化代码，提高可读性；
3. DFS和BFS的本质区别在于数据结构的选择：栈对应深度优先，队列对应广度优先。
