目錄
0.floodfill算法簡介
1.圖像渲染
題解
2.島嶼數量
題解
之前我們在 bfs 中有介紹過[Lc15_bfs+floodfill] 圖像渲染 | 島嶼數量 | 島嶼的最大面積 | 被圍繞的區域，現在我們來看看 dfs 又是如何解決的呢
0.floodfill算法簡介
floodfill算法又叫洪水灌溉或者洪水淹沒
- 比如有一個區域，負數表示低谷，0表示平原，正數表示山峰。
- 此時發大水把這些區域淹了。其中平原和山峰可能不會改變，但是低谷水位就要上升。
- 這種類型題目就是，我們要在這個區域中找出水位會上升的區域或者說找到會被洪水淹的區域。
其實這道題說白了就是把 性質相同的一個連通塊 找出來。
比如這里就是把所有是負數的連通塊找到，注意只能上下左右相連，斜著不能連！
floodfill算法解決的問題就這么簡單，它解決方法也非常簡單
- 可以用深度優先遍歷和寬度優先遍歷。
- dfs就是一條路走到黑，如果無法走就回溯到上一層，然后能走就繼續走，直到走到一個不能走的位置。（上下左右就是每層的選擇，走到葉子節點的時候就找到連通塊啦~）
此時就把一個連通區域找到了。
bfs從一個位置開始把和我相連的位置加入到隊列里，然后繼續在擴一層在擴一層…
- 因此floodfill算法有兩種解決方式，要么dfs、要么bfs。
- 你會發現這個dfs和我們前面單詞搜索，黃金礦工解法非常相似，到一個位置之后就上下左右掃描，當和我性質相同就遞歸進去。
這里主要用的是dfs。bfs在前面的優選算法里面，本質其實就是暴搜。
1.圖像渲染
鏈接：733. 圖像渲染
有一幅以 m x n 的二維整數數組表示的圖畫 image ，其中 image[i][j] 表示該圖畫的像素值大小。你也被給予三個整數 sr , sc 和 color 。你應該從像素 image[sr][sc] 開始對圖像進行上色 填充 。
為了完成 上色工作：
- 從初始像素開始，將其顏色改為
color。 - 對初始坐標的 上下左右四個方向上 相鄰且與初始像素的原始顏色同色的像素點執行相同操作。
- 通過檢查與初始像素的原始顏色相同的相鄰像素并修改其顏色來繼續 重復 此過程。
- 當 沒有 其它原始顏色的相鄰像素時 停止 操作。
最后返回經過上色渲染 修改 后的圖像 。
題解
題目說這么多，其實就是給一個矩陣，在給一個初始的坐標，然后把和這小格性質相同的連通塊找到然后變成newcolor。注意只能上下左右去找！
- 關于題目的詳細解釋，可以去的 BFS 相應文章中查看
class Solution {
public:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int m,n,ret,_color;vector<vector<int>> floodFill
(vector<vector<int>>& image, int sr, int sc, int color)
{m=image.size();n=image[0].size();ret=image[sr][sc];image[sr][sc]=color;_color=color;if(ret==color) return image; //！！！！邊界dfs(image,sr,sc);return image;
}void dfs(vector<vector<int>>& image, int i, int j)
{for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0 && x<m && y>=0 && y<n&& image[x][y]==ret){image[x][y]=_color;dfs(image,x,y);}}
}
};if(ret==color) return image; //！！！！開始前，處理邊界
2.島嶼數量
鏈接：200. 島嶼數量
給你一個由 '1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。
此外，你可以假設該網格的四條邊均被水包圍。
示例 1：
輸入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
輸出：1題解
這道題讓找到由陸地構成的島嶼的數量，也就是讓找到性質相同的連通塊數量。
- 注意只能上下左右找。
- 1代表陸地，0代表水域。
我們一行一行掃描
- 掃描到第一個1的時候，我就把以這個1相連的所有為1的區域都標記一下
- 相當于找到了一塊島嶼記錄一下。
- 接下來繼續掃描。但是有可能會碰到重復的情況，因此這里需要一個bool類型的數組 標記當前位置是否被找過。
- 或者可以修改原始值把它由1變成0。這里我們還用的是老方法bool類型數組。
之前走過下一就不能在走了。
class Solution {
public:int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int ret=0,m,n;vector<vector<bool>> check;int numIslands(vector<vector<char>>& grid) {m=grid.size();n=grid[0].size();check.resize(m,vector<bool>(n,false));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(!check[i][j] && grid[i][j]=='1'){check[i][j]=true;ret++;dfs(grid,i,j);}}}return ret;}void dfs(vector<vector<char>>& grid,int i,int j){for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x>=0 && x<m && y>=0 && y<n&& !check[x][y] &&grid[x][y]=='1'){check[x][y]=true;dfs(grid,x,y);}}}
};- 一，這里的 grid 里是 char（'1')
- 二，要注意一下無論是起始，還是結束都要對 check 進行一個判斷，來防止進入死循環
