给定一个由
'1'（陆地）和'0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。示例 1:
输入: 11110 11010 11000 00000 输出: 1示例 2:
输入: 11000 11000 00100 00011 输出: 3
解法一：
//时间复杂度O(n^2), 空间复杂度O(1)
class Solution {
public:
void dfs(vector<vector<char>>& grid, int i, int j) {
grid[i][j] = '0';
int dx[] = { 0, -1, 1, 0 };
int dy[] = { -1, 0, 0, 1 };
for(int k = 0; k < 4; k++) {
int nexti = i + dx[k], nextj = j + dy[k];
if(nexti >= 0 && nexti < grid.size() &&
nextj >= 0 && nextj < grid[0].size() &&
grid[nexti][nextj] == '1')
dfs(grid, nexti, nextj);
}
}
int numIslands(vector<vector<char>>& grid) {
if(grid.empty()) return 0;
int res = 0;
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[0].size(); j++) {
if(grid[i][j] == '1') {
dfs(grid, i, j);
res++;
}
}
}
return res;
}
};解法一：
DFS。遍历二维数组中的所有元素，如果当前元素是‘1’，说明当前位置在某个小岛上，调用dfs()，该函数将当前所站的小岛清除（将连通区域的‘1’置‘0’）同时计数，直到遍历完成。
有副作用，会改变原二维数组。
2020/01/07 23:16