题解 | #岛屿数量#
岛屿数量
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;
最后返回岛屿数量。
查看18道真题和解析