LeetCode 130- 被圍繞的區(qū)域

題目鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術成長平臺

題目描述：給你一個 m x n 的矩陣 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充。

解題思路（思路一是自己的思路，思路二題解思路，不過用兩種遍歷方式寫出來）

思路一（深度優(yōu)先遍歷）：

我的思路：是開辟一個二維數(shù)組，存儲二元組，來記錄那些下標，首先是一個一維數(shù)組，每次記錄我們當前遍歷島嶼的下標，當被環(huán)繞的時候壓入到二維數(shù)組中，否則直接清空。類似將所有島嶼都淹沒，然后再看哪些島嶼沒被包圍再還原成陸地。

1. 首先確定遞歸函數(shù)的參數(shù)，返回值。覆蓋那些被環(huán)繞的區(qū)域，我們直接設置兩個全局變量vec（存儲所有需要還原的海洋）和tmp（存儲當前我們遍歷的這片島嶼的下標），flag表示是否被包圍，這樣可以不用寫太多參數(shù)傳遞。返回值就是void，參數(shù)需要圖和一個x和y來記錄當前在哪個島嶼。下次從這個島嶼開始走的。
2. 確定終止條件，本題按我們的邏輯，先進入循環(huán)再判斷是否應該終止，那么終止條件就是：當超出網(wǎng)格范圍(這里還需要把flag 設置為false，表示沒被包圍) 或 該島嶼已經(jīng)是海洋 就終止。
3. 單層處理邏輯，每次將當前島嶼淹沒（這里也就是設置為'X'），然后將其下標壓入tmp（為什么有tmp，是因為我們不知道當前的這片島嶼馬上是否要恢復，也就是變成'O'所以需要一個臨時的，當我們確定要恢復的時候就將其壓入到vec中）。

class Solution {
public:bool flag = true; //表示是否被環(huán)繞（只要相連的島嶼有一個在邊界就不是被環(huán)繞的）,被環(huán)繞就不用撤回修改vector<vector<pair<int,int>>> vec;//存所有島嶼下標，其中全都是要變回'O'的vector<pair<int,int>> tmp; //保存當前遍歷這片島嶼的下標，一會可能填充。void dfs(vector<vector<char>> &grid,int x,int y){if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()){flag = false;//表示沒有被環(huán)繞return ;}if(grid[x][y] == 'X') return;tmp.push_back({x,y});//壓入當前島嶼的下標grid[x][y] = 'X';dfs(grid,x+1,y);dfs(grid,x-1,y);dfs(grid,x,y+1);dfs(grid,x,y-1);}void solve(vector<vector<char>>& grid) {int m = grid.size(),n = grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 'O'){dfs(grid,i,j);//當flag為false，也就是島嶼沒有被包圍，我們就將其壓入vec中，最后再還原if(flag == false){vec.push_back(tmp);tmp.clear();//這里注意要把tmp清空了，方便下次使用flag = true;//flag再改為默認值}else{//這里不改flag是因為如果走這個分支，那flag一定還是默認值truetmp.clear();}}}}//將未被包圍的小島嶼還原為'O'for(int i=0;i<vec.size();i++){for(int j=0;j<vec[i].size();j++){grid[vec[i][j].first][vec[i][j].second] = 'O';}}return ;}
};

思路二（廣度優(yōu)先遍歷）：

比較猛的一個思路：本題我們可以看到，只有和邊界相連的O不會變，其余的都得變成X，那么我們可以將與邊界相連的所有O全部變成一個特定符號如'-'，這樣，其中所有的'-'都是與邊界相連的，馬上會再變成'O'。而這個時候圖中所有的'O'都是被包圍的，全都變?yōu)?#39;X'即可。

class Solution {
public:int dir[4][2] = {0,1,1,0,-1,0,0,-1};void bfs(vector<vector<char>> &grid,int x,int y){queue<pair<int,int>> que;que.push({x,y});grid[x][y] = '-';//將與邊界相連的全部變?yōu)?#39;-'//廣度優(yōu)先遍歷while(!que.empty()){pair<int,int> cur = que.front();que.pop();for(int i=0;i<4;i++){int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if(nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size() ||grid[nextx][nexty] != 'O') continue;que.push({nextx,nexty});grid[nextx][nexty] = '-';}}}void solve(vector<vector<char>>& grid) {int row = grid.size(),col = grid[0].size();for(int i=0;i<col;i++){//遍歷第一行的所有列if(grid[0][i] == 'O') bfs(grid,0,i);//遍歷最后一行的所有列if(grid[row-1][i] == 'O') bfs(grid,row-1,i);}for(int i=0;i<row;i++){//遍歷第一列的所有行if(grid[i][0] == 'O') bfs(grid,i,0);//遍歷最后一列的所有行if(grid[i][col-1] == 'O') bfs(grid,i,col-1);}//這個時候圖中所有'-'都是與邊界相連的，所有'O'都是被包圍起來的。for(int i=0;i<row;i++){for(int j=0;j<col;j++){//這倆式子順序反了，導致花了我半小時調(diào)試if(grid[i][j] == 'O')grid[i][j] = 'X';if(grid[i][j] == '-')grid[i][j] = 'O';}}return ;}
};

總結：

• 深搜和廣搜的問題，廣搜里面寫的那個思路很清奇，還是得多看題目的提示，可以減少一點時間和空間的損耗。

LeetCode 417- 太平洋大西洋水流問題

題目鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛的技術成長平臺

題目描述：有一個 m × n 的矩形島嶼，與 太平洋 和 大西洋 相鄰。 “太平洋” 處于大陸的左邊界和上邊界，而 “大西洋” 處于大陸的右邊界和下邊界。

這個島被分割成一個由若干方形單元格組成的網(wǎng)格。給定一個 m x n 的整數(shù)矩陣 heights ， heights[r][c] 表示坐標 (r, c) 上單元格 高于海平面的高度 。

島上雨水較多，如果相鄰單元格的高度 小于或等于 當前單元格的高度，雨水可以直接向北、南、東、西流向相鄰單元格。水可以從海洋附近的任何單元格流入海洋。

返回網(wǎng)格坐標 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水從單元格 (ri, ci) 流動 既可流向太平洋也可流向大西洋 。

解題思路

首先明確本題題意，意思就是雨水高的地方能往雨水低的地方流，要我們求出能流向兩大洋的點坐標。

思路一（深度優(yōu)先遍歷）：

這題總體思路就是遍歷邊界點（也就是能直接流進大洋的點），再逆流遍歷，因為雨水往低處流，我們逆流遍歷就可以找到所有大于邊界的雨水高度的點，這些點就是可以直接流進大洋的點

1. 首先確定遞歸函數(shù)的參數(shù)，返回值。參數(shù)我們需要設置一個isvisited來表示這個點能不能走到其中一個大洋中去。還有x，y坐標來表示當前遍歷到的點的位置
2. 確定終止條件，本題按我們的邏輯，先進入循環(huán)再判斷是否應該終止，那么終止條件就是：當超出網(wǎng)格范圍 或 當前遍歷的是海洋 就跳過。不過這里需要注意，這道題目我們這里的邏輯是逆流而上，所以下一次要去的節(jié)點的雨水高度 小于 我們當前節(jié)點的雨水高度的時候也直接跳過。

1. 單層處理邏輯，每次進入遞歸，我們就將訪問設置為true，代表可以直接流進大洋。不過在處理遍歷的時候有點麻煩，需要注意m和n各表示的是什么，別弄混了。

class Solution {
private:int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四個方向// 從低向高遍歷，注意這里visited是引用，即可以改變傳入的pacific和atlantic的值void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int x, int y) {if (visited[x][y]) return;visited[x][y] = true;for (int i = 0; i < 4; i++) { // 向四個方向遍歷int nextx = x + dir[i][0];int nexty = y + dir[i][1];// 超過邊界if (nextx < 0 || nextx >= heights.size() || nexty < 0 || nexty >= heights[0].size()) continue;// 高度不合適，注意這里是從低向高判斷if (heights[x][y] > heights[nextx][nexty]) continue;dfs (heights, visited, nextx, nexty);}return;}
public:vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {vector<vector<int>> result;int n = heights.size();int m = heights[0].size(); // 這里不用擔心空指針，題目要求說了長寬都大于1// 記錄從太平洋邊出發(fā)，可以遍歷的節(jié)點vector<vector<bool>> pacific = vector<vector<bool>>(n, vector<bool>(m, false));// 記錄從大西洋出發(fā)，可以遍歷的節(jié)點vector<vector<bool>> atlantic = vector<vector<bool>>(n, vector<bool>(m, false));// 從最上最下行的節(jié)點出發(fā)，向高處遍歷for (int i = 0; i < n; i++) {dfs (heights, pacific, i, 0); // 遍歷最上行，接觸太平洋dfs (heights, atlantic, i, m - 1); // 遍歷最下行，接觸大西洋}// 從最左最右列的節(jié)點出發(fā)，向高處遍歷for (int j = 0; j < m; j++) {dfs (heights, pacific, 0, j); // 遍歷最左列，接觸太平洋dfs (heights, atlantic, n - 1, j); // 遍歷最右列，接觸大西洋}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {// 如果這個節(jié)點，從太平洋和大西洋出發(fā)都遍歷過，就是結果if (pacific[i][j] && atlantic[i][j]) result.push_back({i, j});}}return result;}
};

總結：

• 逆流而上的操作，主要是根據(jù)邊界來想到了這個思路。