题解 | #岛屿数量#

岛屿数量

https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e

2022.0831算法第46题岛屿数量

最近学习了递归回溯算法，解决排列，组合，子集，分割字符串和网格问题

排列，组合，子集这三个已经写过，感觉就是模板，最难的操作在于想通树形结构怎么画

同时剪枝的操作也很重要，同时也十分的难想。

岛屿数量这道题，并不是标准的回溯，只是用到了递归。

刚开始有点想法，感觉就是用递归，但是对于具体的思路没想法，不会。

看了解析之后，理解是将每次遇到的1和它连通的区域都赋值为0，这样就一次遇到一个岛屿（连通域）

这样感觉还没回溯好想，总会有一些具体的代码或者过程想不通

刚开始边界处理我就想的比较复杂，想着这样就太麻烦了

结果看了代码明白不用考虑那么多情况，每次子需要保证当前函数的参数是有意义的就行。

下面介绍一下解题思路：

首先，需要编写dfs函数，将连通的区域都赋值为0，

需要指出当前格子的位置，（i，j）

并且需要对i，j进行边界判断，只处理符合要求的位置，并且要指定迭代跳出的条件

遇到0就停止迭代

//刚开始想到了边界，但是觉着很麻烦，其实还是自己想复杂了
//边界条件，[0-size)，要确保i和j正确，比如i=0时，i-1就不用考虑了
if(i<0||i>=grid.size()||j<0||j>=grid[0].size()||grid[i][j]=='0')
    return ;

然后每调用一次就将当前位置赋为0，

重复对四个邻居调用

grid[i][j]='0';
//对相邻的四个格子进行处理，这时候不需要考虑边缘格子
//边缘格子会直接进行处理
dfs(grid,i-1,j);//上
dfs(grid,i,j-1);//左
dfs(grid,i+1,j);//下
dfs(grid,i,j+1);//右

这样dfs函数就写好了，能够将一片连通域全部赋为0

void dfs(vector<vector<char> >& grid,int i,int j){
    //刚开始想到了边界，但是觉着很麻烦，其实还是自己想复杂了
    //边界条件，[0-size)，要确保i和j正确，比如i=0时，i-1就不用考虑了
    if(i<0||i>=grid.size()||j<0||j>=grid[0].size()||grid[i][j]=='0')
        return ;
    //将此时的位置赋为0
    grid[i][j]='0';
    //对相邻的四个格子进行处理，这时候不需要考虑边缘格子
    //边缘格子会直接进行处理
    dfs(grid,i-1,j);//上
    dfs(grid,i,j-1);//左
    dfs(grid,i+1,j);//下
    dfs(grid,i,j+1);//右   
}

在主函数中进行调用，

首先要确保网格非空

//确保网格中有一个数grid[0]有意义
if(grid.size()==0)
    return 0;
//记录岛屿的数量（连通的个数）
int nums=0;

之后遍历网格，将每个岛屿改变属性。

//遍历网格
for(int i=0;i<grid.size();i++){
    for(int j=0;j<grid[0].size();j++){
        //当遇到为1的网格，调用dfs，将相通的格子都赋值为0
        //没遇到一次1，则代表一个岛屿（一片区域）
        if(grid[i][j]=='1'){
            dfs(grid,i,j);
            nums++;
        }                
    }
}
//返回岛屿个数
return nums;

最后返回岛屿数量。

#算法题#