LeetCode 200.岛屿数量

目录

题目：

题目描述：

题目链接：

思路：

核心思路：

思路详解：

代码：

Java代码：

---

题目：

题目描述：

题目链接：

200. 岛屿数量 - 力扣（LeetCode）

思路：

核心思路：

深搜 - dfs

思路详解：

题目核心语句：每座岛屿只能由水平方向/竖直方向上相邻的陆地连接形成

所以思路就是遍历二维网络的每一个位置，判断是陆地还是水。如果遍历到的是陆地，那么就从这块陆地开始不断以上下左右的方向往外寻找陆地进行拓展，拓展到的陆地还可以接着按照这个规则往外拓展。直到无法进行拓展为止，此时一开始遍历到的陆地再加上所有拓展到的陆地才算一个岛屿。

所以我们要定义dfs函数来实现，为了防止已经被拓展过的陆地被重复搜索，我们每次可以设置grip[x][y]='2'表示当前搜索到的陆地已经被拓展。而dfs的终止条件就是先进行边界判断，判断是否超出行和列，再判断是否是水或者是已经被拓展的陆地。最后在dfs函数中按照向上拓展，向下拓展，向左拓展，向右拓展的规则递归即可实现搜索完一整个岛屿的功能。

代码：

Java代码：

class Solution {private int ans;  //ans记录岛屿数量的结果private char[][] grid;  //按照题意定义二维字符数组gripprivate int row;  //row表示行数private int column;  //column表示列数public int numIslands(char[][] grid) {this.grid=grid;this.row=grid.length;this.column=grid[0].length;for(int i=0;i<row;i++)  //遍历grip的每一处{for(int j=0;j<column;j++){if(grid[i][j]=='1')  //如果遍历到陆地{ans++;  //岛屿数量加1dfs(i,j);  //深搜，从这块陆地按照指定规则不断向外拓展//该陆地再包括所有拓展到的陆地才算一个岛屿}}}return ans;}private void dfs(int x, int y)  //定义深搜函数dfs{//判断是否超出行与列的边界，再判断是否是水或者是已经被拓展过的陆地if(x<0||x>=row||y<0||y>=column||grid[x][y]=='0'||grid[x][y]=='2'){return;}grid[x][y]='2';  //设置为2表示该陆地已经被拓展过dfs(x-1,y);  //向上拓展dfs(x+1,y);  //向下拓展dfs(x,y-1);  //向左拓展dfs(x,y+1);  //向右拓展}
}