如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
1.每日一题
2.解题思路：DFS
深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。
2.1思路分析
整体思路就是找到一堆1就意味着找到一个岛屿，然后把他们变成0，再找下一堆1再把这堆1变成0，直到没有1为止。
微观上的处理就是：当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0，因此可以用递归实现。
- step 1：首先还是要做特例检查，矩阵不能为空*且长度不能为0
- step 2：然后找到一个1作为起始点，把与这个1相连的所有1置为0（这一步使用递归来实现）
- step 3：找到一个1后，遍历它的四周看看还有没有1，如果有则进入更深层次的递归去找到这个1周围的1，统统把它们变为0，如此递归下去直到这片区域没有1这次递归才结束
- step 4：然后重新找一个起始点，重复第step 3步，直到双层for循环遍历完整个矩阵再也找不到1了
2.2核心代码
importjava.util.*;
publicclassSolution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
//记录岛屿数量
privateintans;
//搜索的方向数组
privateintxx[]={-1,1,0,0};
privateintyy[]={0,0,-1,1};
publicintsolve (char[][] grid) {
//数组为空检查
if(grid==null||grid.length==0){
return0;
}
//初始化岛屿数量为0
ans=0;
//数组的行
intr=grid.length;
//数组的宽
intc=grid[0].length;
//遍历数组矩阵找到初始点(1)
for(inti=0;i<r;++i){
for(intj=0;j<c;++j){
if(grid[i][j]=='1'){
//岛屿数量++
ans++;
//深搜将与这个(1)相连的所有1置为0
dfs(i,j,grid);
}
}
}
returnans;
}
publicvoiddfs(intx,inty,char [][]grid){
//搜索的结束条件,数组越界或者此点不是1(陆地)就结束
if(!check(x,y,grid)){
return;
}
//此点被搜索过,将1置为0
grid[x][y]=0;
//扩展向上下左右四个方向搜索
for(inti=0;i<4;++i){
intdx=x+xx[i];
intdy=y+yy[i];
//剪枝操作：越界检查以及检查此点是不是陆地
if(check(dx,dy,grid)){
dfs(dx,dy,grid);
}
}
}
//剪枝操作
publicbooleancheck(intx,inty,char [][]grid){
if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&grid[x][y]=='1'){
returntrue;
}
returnfalse;
}
}
3.解题思路：BFS
广度优先搜索与深度优先搜索不同，它是将与某个节点直接相连的其它所有节点依次访问一次之后，再往更深处，进入与其他节点直接相连的节点。
bfs的时候我们常常会借助队列的先进先出，因为从某个节点出发，我们将与它直接相连的节点都加入队列，它们优先进入，则会优先弹出，在它们弹出的时候再将与它们直接相连的节点加入，由此就可以依次按层访问。
用bfs解此题整体思路还是一样的，统计岛屿的方法可以和dfs同样遍历解决，为了去重我们还是要将所有相邻的1一起改成0，这时候同样遍历连通的广度优先搜索（bfs）可以代替dfs。
3.1思路分析
- step 1：首先还是要做特例检查，矩阵不能为空*且长度不能为0
- step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
- step 3：使用bfs将遍历矩阵遇到的1以及相邻的1全部置为0：利用一个队列来实现，每次队列把搜索到的第一个1加入队列中，然后然后向此点的上下左右四个方向扩展搜索
- step 4：把搜索到的每一个为1的点都标记为0，目的是去重，防止重复搜索
- step 5：直至队列为空时，说明此区域的1全被搜索完（都被置为0了）一次广搜结束，代表找到一个岛屿
- step 6：回到solution的双重for循环重复step 2,3,4,5步直至矩阵中所有的点都被遍历
3.2核心代码
importjava.util.*;
classNode{
intx,y;
publicNode(intx,inty){
this.x=x;
this.y=y;
}
}
publicclassSolution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
privateintans;
privateint[][]vis;
privateint[] xx={-1,1,0,0};
privateint[] yy={0,0,-1,1};
publicintsolve (char[][] grid) {
// write code here
intn=grid.length;
intm=grid[0].length;
vis=newint[n][n];
for(inti=0;i<n;++i){
for(intj=0;j<m;++j){
if(grid[i][j]=='1'){
ans++;
grid[i][j]='0';
bfs(newNode(i,j),grid,n,m);
}
}
}
returnans;
}
voidbfs(Nodenode,char[][] grid,intn,intm){
Queue<Node>q=newLinkedList<Node>();
q.add(node);
while(!q.isEmpty()){
Nodenow=q.poll();
if(now.x<0&&now.y<0&&now.x>=n&&now.y>=m){
break;
}
for(intt=0;t<4;++t){
intdx=now.x+xx[t];
intdy=now.y+yy[t];
if(dx>=0&&dy>=0&&dx<n&&dy<m&&grid[dx][dy]=='1'){
grid[dx][dy]='0';
q.add(newNode(dx,dy));
}
}
}
}
}
📚订阅专栏：『牛客刷题集锦』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
-
