1.题目

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回 网格坐标 result 的 2D列表 ，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
image.png

  1. 输入: heights = [[2,1],[1,2]]
  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

    2.思路

    模拟，通过对每个方块的水流进行模拟，在四个方向上寻找，判断是否可以流到边界。但是这样顺着寻找的话，时间复杂度会比较高，考虑水流的逆流，从四条边界反向寻找，如果当前方块没有被访问过，那么将其状态设为以访问的状态，并判断是否可以访问当前方块的相邻方块（即相邻方块的高度值是否大于当前方块高度值，大于则访问改相邻方块）。从上边界和左边界开始搜索获得的是可以流入太平洋的方块，从下边界和有边界开始搜索获得的是可以流入大西洋的方块，两种均为真则放入最后的结果中。

    3.代码

    1. static const int d[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};
    2. class Solution {
    3. public:
    4.   vector<vector<int>> heights;
    5.   void dsf(int posi, int posj, vector<vector<bool>>& ocean)
    6.   {
    7.       int m = ocean.size(), n = ocean[0].size();
    8.       if(ocean[posi][posj])
    9.       {
    10.           return;
    11.       }
    12.       ocean[posi][posj] = true;
    13.       //cout << "posi: " << posi << " posj:" << posj
    14.       for(int i = 0; i < 4; i++)
    15.       {
    16.           int newi= posi + d[i][0], newj = posj + d[i][1];
    17.           if(newi >=0 && newi<m && newj>=0 && newj < n && heights[newi][newj] >= heights[posi][posj])
    18.               dsf(newi, newj, ocean);
    19.       }
    20.   }
    21.   vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    22.       vector<vector<int>> ans;
    23.       this->heights = heights;
    24.       int m = heights.size(), n = heights[0].size();
    25.       vector<vector<bool>> p(m, vector<bool>(n, false));
    26.       vector<vector<bool>> a(m, vector<bool>(n, false));
    28.       for(int i = 0; i < m; i++)
    29.       {
    30.           dsf(i, 0, p);
    31.       }
    32.       for(int i = 0; i < n; i++)
    33.       {
    34.           dsf(0, i, p);
    35.       }
    36.       for(int i = 0; i < n; i++)
    37.       {
    38.           dsf(m-1, i, a);
    39.       }
    40.       for(int i = 0; i  < m; i++)
    41.       {
    42.           dsf(i, n-1, a);
    43.       }
    45.       for(int i = 0; i < m; i++)
    46.       {
    47.           for(int j = 0; j < n; j++)
    48.           {
    49.               if(a[i][j] && p[i][j])
    50.               {
    51.                   vector<int> cell;
    52.                   cell.emplace_back(i);
    53.                   cell.emplace_back(j);
    54.                   ans.emplace_back(cell);
    55.               }
    56.           }
    57.       }
    58.       return ans;
    59.   }
    60. };