題目描述

有一個?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

解決方案：

1、分析問題求解：水從一定高度可以流向上（左）和下（右）兩種邊界低處，其高度不一定是最高

2、兩種情況分別討論：從上或左 || 從下或右

3、逆向思維：從低處到高處，正向遍歷，解集合：兩種情況的高度都有重合即是答案

函數源碼：

class Solution {
public:vector<int> direction{-1,0,1,0,-1};void dfs(vector<vector<int>>& heights,vector<vector<bool>>&reach,int row,int col){if(reach[row][col])     return;//結束條件：reach[row][col]=true;int x,y;for(int i=0;i<4;i++){x=row+direction[i],y=col+direction[i+1];//轉化為上下左右四格的位置if( x>=0 && x<heights.size() && y>=0 && y<heights[0].size() &&heights[row][col]<=heights[x][y]){dfs(heights,reach,x,y);//row=x;col=y;更新位置}}}vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {if(heights.empty()||heights[0].empty())     return {};vector<vector<int>> ans;int row=heights.size();int col=heights[0].size();vector<vector<bool>> p(row,vector<bool>(col,false)); vector<vector<bool>> a(row,vector<bool>(col,false));for(int i=0;i<row;i++){//左邊界，右邊界dfs(heights,p,i,0);dfs(heights,a,i,col-1);}for(int i=0;i<col;i++){//上邊界，下邊界dfs(heights,p,0,i);dfs(heights,a,row-1,i);}for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(p[i][j]&&a[i][j]){ans.push_back(vector<int>{i,j});}}}return ans;}
};