来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
题目描述
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回 网格坐标 result 的 2D列表 ，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。
示例 1：
输入: 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]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2：
输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
提示：
m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105
解题思路
中文的翻译题目让人很难理解，其实就是判断每个格子是否能将水同时流到大西洋和太平洋中，如果自顶而下一个一个格子的判断，那么时间复杂度将会达到O(m2n2)，所以采用边缘自底而上的方法，只需要对每个边缘的格子进行dfs判断，然后做好标记，最终遍历标记图，将同时有两种标记的格子写入输出中。由于每个格子都仅被访问一次，所以时间复杂度为O(mn)
代码展示
class Solution { public: vector<vector<int>> m_vvi_Flag; int m_i_Row; int m_i_Col; vector<vector<int>> m_heights; void dfs(int h, int row, int col, int type) { if(row < 0 || row >= m_i_Row || col < 0 || col >= m_i_Col) return ; if(h > m_heights[row][col]) return; if((m_vvi_Flag[row][col] & type) == type) return ; m_vvi_Flag[row][col] |= type; dfs(m_heights[row][col], row + 1, col, type); dfs(m_heights[row][col], row - 1, col, type); dfs(m_heights[row][col], row, col + 1, type); dfs(m_heights[row][col], row, col - 1, type); } vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) { vector<vector<int>> vvi_Ret; m_heights = heights; m_i_Row = heights.size(); m_i_Col = heights[0].size(); m_vvi_Flag.resize(m_i_Row, vector<int>(m_i_Col)); for(int i = 0; i < m_i_Col; i++) { dfs(-1, 0, i, 1); dfs(-1, m_i_Row - 1, i, 2); } for(int i = 0; i < m_i_Row; i++) { dfs(-1, i, 0, 1); dfs(-1, i, m_i_Col - 1, 2); } for(int i = 0; i < m_i_Row; i++) for(int j = 0; j < m_i_Col; j++) { if(m_vvi_Flag[i][j] == 3) { vvi_Ret.push_back({i, j}); } } return vvi_Ret; } }; 运行结果
