岛屿数量

几个月前才做过这道题,当时没做出来,花了点时间看题解,结果现在又刷到,还是没有思路😭,再来!

LeetCode 中,「岛屿问题」是一个系列问题,如果你看到这了,不妨再尝试以下解决下面几道题:(这里透露一个小技巧,中文输入法下输入uubd可以打出类似「」等各种符号)

DFS 基本结构

先理解二叉树上的 DFS 遍历:

void traverse(TreeNode root){
// 判断 base case
if(root == null) return;
// 递归访问左右子树
traverse(root.left);
traverse(root.right);
}

两个要素:

  1. 访问相邻节点

    对于二叉树,即递归访问左右子树

  2. 判断 base case

    对于二叉树,即判断 root == nullroot 指向的子树为空了,就不需要再往下遍历了

类比网格:

  1. 相邻节点」:上下左右四个,对于格子(r, c)来说(r 和 c 分别代表行坐标和列坐标),四个相邻的格子分别是 (r-1, c)(r+1, c)(r, c-1)(r, c+1)。换句话说,网格结构是「四叉」的。
  2. 判断 base case」:类比二叉树应该是不需要再遍历的格子,即超出网格范围(数组下标越界的格子)

得到网格 DFS 遍历的代码:

void dfs(int[][] grid,int r,int c){
// 判断 base case
// 如果坐标超出网格范围,直接返回
if(!inArea(grid,r,c)){
return;
}
// 访问上下左右四个相邻节点
dfs(grid,r - 1,c);
dfs(grid,r + 1,c);
dfs(grid,r,c - 1);
dfs(grid,r,c + 1);
}
// 判断坐标(r,c) 是否超出网格范围
boolean inArea(int[][] grid,int r,int c){
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}

如何避免重复遍历

网格结构的 DFS 与二叉树的 DFS 最大的不同之处在于,遍历中可能遇到遍历过的结点。这是因为,网格结构本质上是一个「图」,我们可以把每个格子看成图中的结点,每个结点有向上下左右的四条边。在图中遍历时,自然可能遇到重复遍历结点。

这时候,DFS 可能会不停地「兜圈子」,永远停不下来。

![DFS 重复遍历](https://blog-vanh.oss-cn-hangzhou.aliyuncs.com/image/DFS 重复遍历.gif)

解决方案:标记已经遍历过的格子。(比如,岛屿问题中,走过的陆地格子把值改为2,区分于1)

改良代码:

void dfs(int[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿,直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」

// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}

// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}

![解决 DFS 重复遍历](https://blog-vanh.oss-cn-hangzhou.aliyuncs.com/image/解决 DFS 重复遍历.gif)

岛屿数量问题代码

class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i = 0;i < grid.length;i++){
for(int j = 0;j < grid[0].length;j++){
if(grid[i][j] == '1'){
// 遍历所有的陆地并将其重置为海洋
dfs(grid,i,j);
// 岛屿数量 + 1
count++;
}
}
}
return count;
}
public void dfs(char[][] grid,int i,int j){
if(!inArea(grid,i,j)){
return;
}
if(grid[i][j] == '0'){
return;
}
grid[i][j] = '0';
dfs(grid,i - 1,j);
dfs(grid,i + 1,j);
dfs(grid,i,j - 1);
dfs(grid,i,j + 1);
}
public boolean inArea(char[][] grid,int i,int j){
return 0 <= i && i < grid.length
&& 0 <= j && j < grid[0].length;
}
}