給你一個由?'1'（陸地）和?'0'（水）組成的的二維網格，請你計算網格中島嶼的數量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設該網格的四條邊均被水包圍。

解題思路：

? ? ? ? // 類比二叉樹的dfs方法； 遞歸檢查左右子樹

? ? ? ? // 將網格中的元素看作一個四叉的 就有四個（（看作四個子樹），不同在于會出現重復遍歷兜圈子

? ? ? ? // 因此需要在每個格子元素遍歷后將其加一個標志 true 表示遍歷過，false 表示沒有遍歷

class Solution {
public:int numIslands(vector<vector<char>>& grid) {// 類比二叉樹的dfs方法； 遞歸檢查左右子樹// 將網格中的元素看作一個四叉的 就有四個（（看作四個子樹），不同在于會出現重復遍歷兜圈子// 因此需要在每個格子元素遍歷后將其加一個標志 true 表示遍歷過，false 表示沒有遍歷// 二叉樹// dfs(treenode *root){// if (root == null) {//     return;// }// // 訪問兩個相鄰結點：左子結點、右子結點// dfs(root.left);// dfs(root.right);// }// 網格深度優先遍歷// void grid_dfs(vector<vector<char>>& grid,vector<vector<bool>>& grid_judg ,int r,int c){//     if(r > grid.size() || c > grid[0].size() || r<0 || c<0){ // 超出網格范圍//         return; //     }//     //     if(grid_jude[r][c] || grid[r][c] !=1 ){ // 判斷是否為遍歷過的島嶼//         return; //     }//     grid_jude[r][c] = true;//     grid_dfs(grid,r-1,c); // 上面//     grid_dfs(grid,r+1,c); // 下面//     grid_dfs(grid,r,c-1); // 左面//     grid_dfs(grid,r,c+1); // 右面// }if (grid.empty() || grid[0].empty()) {return 0; // 如果網格為空，直接返回 0}int row = grid.size(), col = grid[0].size();int res = 0;vector<vector<bool>> grid_judg(row, vector<bool>(col, false)); // 保存是否遍歷過for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {if (grid[i][j] == '1' && !grid_judg[i][j]) {++res; // 發現一個新的島嶼grid_dfs(grid, grid_judg, i, j); // 遞歸標記整個島嶼}}}return res;}void grid_dfs(vector<vector<char>>& grid, vector<vector<bool>>& grid_judg, int r, int c) {// 邊界條件檢查if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size()) {return; // 超出網格范圍}// 如果當前格子是水或已經訪問過，直接返回if (grid[r][c] != '1' || grid_judg[r][c]) {return;}// 標記當前格子為已訪問grid_judg[r][c] = true;// 遞歸訪問上下左右四個方向grid_dfs(grid, grid_judg, r - 1, c); // 上面grid_dfs(grid, grid_judg, r + 1, c); // 下面grid_dfs(grid, grid_judg, r, c - 1); // 左面grid_dfs(grid, grid_judg, r, c + 1); // 右面}
};

dfs：

將網格中的元素看作一個四叉的 就有四個（（看作四個子樹），不同在于會出現重復遍歷兜圈子

因此需要在每個格子元素遍歷后將其加一個標志 true 表示遍歷過，false 表示沒有遍歷。

      void grid_dfs(vector<vector<char>>& grid,vector<vector<bool>>& grid_judg ,int r,int c){if(r > grid.size() || c > grid[0].size() || r<0 || c<0){ // 超出網格范圍return; }if(grid_jude[r][c] || grid[r][c] !=1 ){ // 判斷是否為遍歷過的島嶼return; }grid_jude[r][c] = true;grid_dfs(grid,r-1,c); // 上面grid_dfs(grid,r+1,c); // 下面grid_dfs(grid,r,c-1); // 左面grid_dfs(grid,r,c+1); // 右面}