1.题目
https://leetcode-cn.com/problems/number-of-islands/
2.题解
这道题我第一个反应出来的解法就是DFS；
DFS，Depth First Search。深度度优先搜索，这原本是来自树结构的算法，就是必须将一个节点下的所有的节点都搜索玩，才对下一个节点进行搜索。意思就是以此题论，每次的搜索都要往四周发散一下，知道四周没有1，再也无法继续往下搜索为止。
应用于这道题目的思路就是以下几种情况：
情况一：第一个1，岛屿数加1；
情况二：四周都是0，岛屿数加1；
我们将水平和垂直相连的部分看成一个整体，那么这个东西就简单了。当我们遇到1的时候，我们岛屿数加1，并使用BFS对四周继续进行判断，是自己人（相邻的1）就直接把他拉进来并且将他设置为0，避免干扰；不是就直接return；直到再遇到下一个1，循坏往复，便可以得到所有的岛屿；
3.代码
class Solution {
public int numIslands(char[][] grid) {
if(grid==null|| grid.length == 0 || grid[0].length == 0){
return 0;
}
int rows=grid.length;//行
int cols=grid[0].length;//列
int result=0;
for(int i=0;i<rows;i++){
for (int j=0; j<cols; j++) {
if(grid[i][j]=='1'){
result++;
bfsInstand(i,j,rows,cols,grid);
}
}
}
return result;
}
private static void bfsInstand(int i,int j,int rows,int cols,char[][] grid){
if(i<0||i>=rows||j<0||j>=cols){
return;
}
if(grid[i][j]=='0'){
return;
}
grid[i][j]='0';
bfsInstand(i+1,j,rows,cols,grid);
bfsInstand(i,j+1,rows,cols,grid);
bfsInstand(i-1,j,rows,cols,grid);
bfsInstand(i,j-1,rows,cols,grid);
}
}
4.结果截图
image.png
