給你一個(gè)由?'1'（陸地）和?'0'（水）組成的的二維網(wǎng)格，請你計(jì)算網(wǎng)格中島嶼的數(shù)量。

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

此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

示例 1：

輸入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
輸出：1

示例 2：

輸入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
輸出：3

思路一：DFS

c++解法

class Solution {
public:void dfs(vector<vector<char>>& grid,int i,int j,int m,int n){if(i<0 || i>=m || j<0 || j>=n || grid[i][j] == '0')return;grid[i][j] = '0';dfs(grid,i + 1,j,m,n);dfs(grid,i - 1,j,m,n);dfs(grid,i,j + 1,m,n);dfs(grid,i,j - 1,m,n);}int numIslands(vector<vector<char>>& grid) {int m = grid.size();int n = grid[0].size();int num = 0;for(int i=0;i<m;i++)for(int j=0;j<n;j++){num += grid[i][j] - '0';dfs(grid,i,j,m,n);}return num;}
};

分析：

本題為島嶼類問題，可用dfs的方式解決，深度搜索將每個(gè)遍歷過的格子賦值為2即標(biāo)記為已遍歷，后面根據(jù)題目需要輸出答案，本題是將每個(gè)島嶼遍歷一遍，當(dāng)?shù)较乱粋€(gè)未遍歷的島嶼返回值加一

總結(jié)：

本題考察對dfs的應(yīng)用，利用dfs每當(dāng)遍歷到一個(gè)未計(jì)數(shù)的島嶼則使用dfs將其設(shè)為已遍歷的島嶼