问题
![]()
代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
//算法思路：既能流向大西洋 ，又能流向太平洋 ，并且水往低处流
//正向寻找这样的点线会使得代码复杂，时间复杂度较大O((mn)*(mn))
//反向思路使用非递归DFS，递归DFS可能会因网格过深导致栈溢出，所以用栈模拟递归实现，更加稳定
class Solution {
private:
// 定义4个方向：上下左右（行和列的偏移量）
vector<vector<int> > dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
// 存储网格的总行数和总列数
int rows, cols;
//heights 地形高度网格,visited 标记数组，记录该位置是否能到达对应海洋
//y 当前起始点的列坐标,x 当前起始点的行坐标
// 坐标合法性检查：判断(r,c)是否在网格内
bool isValid(int x ,int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
void dfs_iter(vector<vector<int> >& heights, int x, int y, vector<vector<bool> >& visited) {
// 用栈来模拟递归，存储待访问的坐标
stack<pair<int, int> > st;//栈的初始化 ，使得可存储坐标对类型
st.push({x, y});// 起始点入栈
visited[x][y] = true;//标记为已访问,避免重复
// 栈不为空时循环（非递归DFS的核心）
while (!st.empty()) {
// 取出栈顶元素（当前访问的坐标）
// 取出栈顶的pair对象
pair<int, int> cur = st.top();
st.pop();
// 分别赋值给cur_x和cur_y
int cur_x = cur.first;
int cur_y = cur.second;
// 遍历4个方向
for (auto& dir : dirs) {
// 计算相邻位置的坐标
int nx = cur_x + dir[0], ny = cur_y + dir[1];
// 边界条件判断：
// 1. 坐标在网格范围内
// 2. 该位置未被访问过
// 3. 相邻位置的高度 >= 当前位置高度（水往低处流，反向就是高处能流向当前处）
if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !visited[nx][ny] && heights[nx][ny] >= heights[cur_x][cur_y]) {
// 标记该位置可到达，并入栈等待后续遍历
visited[nx][ny] = true;
st.push({nx, ny});
}
}
}
}
public:
/**
* 找出既能流向太平洋又能流向大西洋的所有位置
* @param heights 地形高度网格
* @return 满足条件的坐标列表
*/
vector<vector<int> > pacificAtlantic(vector<vector<int> >& heights) {
// 存储最终结果：满足条件的坐标对
vector<vector<int> > res;
// 边界处理：如果网格为空，直接返回空结果
if (heights.empty()) return res;
// 初始化总行数和总列数
rows = heights.size(), cols = heights[0].size();
// pacific[i][j]：标记(i,j)位置的水能否流向太平洋
vector<vector<bool> > pacific(rows, vector<bool>(cols, false));
// atlantic[i][j]：标记(i,j)位置的水能否流向大西洋
vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
// 初始化边界：从太平洋的边界开始DFS
// 第一行（顶部边界）的所有位置，都能直接流向太平洋
for (int j = 0; j < cols; j++) {
dfs_iter(heights, 0, j, pacific);
// 最后一行（底部边界）的所有位置，都能直接流向大西洋
dfs_iter(heights, rows-1, j, atlantic);
}
// 初始化边界：从大西洋的边界开始DFS
// 第一列（左侧边界）的所有位置，都能直接流向太平洋
for (int i = 0; i < rows; i++) {
dfs_iter(heights, i, 0, pacific);
// 最后一列（右侧边界）的所有位置，都能直接流向大西洋
dfs_iter(heights, i, cols-1, atlantic);
}
// 补充：原代码缺失了结果收集的逻辑，这里补上
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; 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, 7, 1, 4, 5},
{5, 1, 1, 2, 4}
};
Solution sol;
vector<vector<int>> res = sol.pacificAtlantic(heights);
cout << "===== 沿海生态保护区规划 - 关键水资源连通区域 =====" << endl;
cout << "场景说明：这些区域是海陆水资源循环的核心，对生态保护至关重要" << endl;
cout << "关键区域坐标（行, 列）：" << endl;
for (auto& pos : res) {
cout << "(" << pos[0] << ", " << pos[1] << ")" << endl;
}
cout << "====================================================" << endl;
return 0;
}
思路解释
寻求既能流向太平洋又能流向大西洋的点，按照水往低处流的自然规律进行，正向解决过于复杂，时间复杂度O（（mn）*（mn）），遂采取反向搜索，从边界出发，从小到大分别寻找可以流入大西洋和太平洋的点，并取两个集合的交集，保证其既能流入大西洋又能流入太平洋。因为递归DFS方法可能因为网格过深而导致溢出，所以采用栈模拟DFS方法。
先定义网格的行列，以及网格遍历周围点的移动数组并且设置循环检验点的合法化，然后定义初始化栈，并且设置起始点入栈并且进行标记，然后对不控的站进行处理：先取出栈顶元素然后重新设置一个值分别表示为取出的栈顶的点的行纵坐标经过移动的值，依次遍历取出点上下左右四个方向的点是否满足在网格内并且周围点的值大于取出点的值，然后用atlantic标记大西洋，用pacific标记太平洋，最后去两个集合的交集，得出测试结果
