题目描述
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water。
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2s:
Input: <br>
11000 <br>
11000 <br>
00100 <br>
00011 <br>
Output: 3 <br>
解题思路
- dfs
- 参考
- 程序写的时候，比较巧妙，访问这个二维数组，如果是1的话，就直接加，然后对这个元素进行dfs搜索，
- 其中搜索的过程，就是上个元素的周围将1变为0的过程，（我们标志0是访问状态）
暴力版本 报超时
C++代码
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int row = grid.size();
if(row == 0){
return 0;
}
int col = grid[0].size();
int res = 0;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
res += grid[i][j] - '0';
dfs(i, j, row, col, grid);
}
}
return res;
}
void dfs(int r, int c, int row, int col, vector<vector<char> >& grid){
if(r < 0 || r >= row || c < 0 || c >= col || grid[r][c] == '0'){
return;
}
grid[r][c] = '0';
dfs(r + 1, c, row, col, grid);
dfs(r - 1, c, row, col, grid);
dfs(r, c + 1, row, col, grid);
dfs(r, c - 1, row, col, grid);
}
};
0205解题思路
- 首先基本思路是正确的
- 就是利用dfs，深度优先遍历，两层循环，遍历完当前元素时，利用dfs，将以其元素为点的元素的周围都改变为0
- 最后统计错了，不应该在递归函数下面将结果进行累加，这样很明显结果偏大
- 其实结果是比较讨巧，就是在遍历的时候就将结果进行累加就行
- 有一个注意的点，传值的时候 形参应该是修改后的引用，不然利用dfs修改值就没有意义啊。。。
