岛屿问题

岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。本文分析DFS算法。

一、框架

因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个 visited 布尔数组防止走回头路

// 二维矩阵遍历框架
func dfs(grid [][]int, i, j int, visited [][]bool) {
    // 超出索引
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
        return
    }
    // 已经遍历过（i, j）
    if visited[i][j] {
        return
    }
    // 进入节点（i, j）
    visited[i][j] = true
    dfs(grid, i-1, j) // 上
    dfs(grid, i+1, j) // 下
    dfs(grid, i, j-1) // 左
    dfs(grid, i, j+1) // 右
}

二、真题

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
eg: 如图，岛屿数量为4

image.png

func numIslands(grid [][]byte) int {
    var result int
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                result++
                dfs(grid, i, j)
            }
        }
    }
    return result
}

// 从（i, j)开始，将与之相邻的陆地都变成海水
func dfs(grid [][]byte, i, j int) {
    // 超出索引边界
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
        return
    }
    // 已经是海水了
    if grid[i][j] == '0' {
        return
    }
    // 将 (i, j) 变成海水
    grid[i][j] = '0'
    // 淹没上下左右的陆地
    dfs(grid, i-1, j)
    dfs(grid, i+1, j)
    dfs(grid, i, j-1)
    dfs(grid, i, j+1)
}

为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。因为 dfs 函数遍历到值为 0 的位置会直接返回，所以只要把经过的位置都设置为 0，就可以起到不走回头路的作用。

PS：这类 DFS 算法还有个别名叫做 [FloodFill 算法]

1254. 统计封闭岛屿的数目

有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。请返回封闭岛屿的数目。
eg: 如下图，封闭岛屿数量为2

image.png

思路：把靠边的岛屿排除掉，剩下的就是「封闭岛屿」

func closedIsland(grid [][]int) int {
    n, m := len(grid), len(grid[0])
    for j := 0; j < m; j++ {
        // 把靠上边的岛屿淹掉
        dfs(grid, 0, j)
        // 把靠下边的岛屿淹掉
        dfs(grid, n-1, j)
    }
    for i := 0; i < n; i++ {
        // 把靠左边的岛屿淹掉
        dfs(grid, i, 0)
        // 把靠右边的岛屿淹掉
        dfs(grid, i, m-1)
    }
    var result int
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if grid[i][j] == 0 {
                result++
                dfs(grid, i, j)
            }
        }
    }
    return result
}

func dfs(grid [][]int, i, j int) {
    // 超出索引边界
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
        return
    }
    // 已经是海水了
    if grid[i][j] == 1 {
        return
    }
    // 将 (i, j) 变成海水
    grid[i][j] = 1
    // 淹没上下左右的陆地
    dfs(grid, i-1, j)
    dfs(grid, i+1, j)
    dfs(grid, i, j-1)
    dfs(grid, i, j+1)
}

695. 岛屿的最大面积

思路：在 dfs 函数淹没岛屿的同时，记录这个岛屿的面积，即 dfs 函数设置返回值，记录每次淹没的陆地的个数。

func maxAreaOfIsland(grid [][]int) int {
    var maxArea int
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                maxArea = max(maxArea, dfs(grid, i, j))
            }
        }
    }
    return maxArea
}

func dfs(grid [][]int, i, j int) int {
    // 超出索引边界
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
        return 0
    }
    // 已经是海水了
    if grid[i][j] == 0 {
        return 0
    }
    // 将 (i, j) 变成海水
    grid[i][j] = 0
    // 淹没上下左右的陆地
    return dfs(grid, i, j-1) + dfs(grid, i, j+1) + dfs(grid, i-1, j) + dfs(grid, i+1, j) + 1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

1905. 统计子岛屿

eg:如下图，子岛屿数量为红色部分，3个

image.png

思路：当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。那么，我们只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。

func countSubIslands(grid1 [][]int, grid2 [][]int) int {
    // 岛屿2中存在一片陆地，在岛屿1的对应位置是海水，那么岛屿2就不是岛屿1的子岛
    for i := 0; i < len(grid2); i++ {
        for j := 0; j < len(grid2[0]); j++ {
            if grid1[i][j] == 0 && grid2[i][j] == 1 {
                dfs(grid2, i, j)
            }
        }
    }

    var result int
    for i := 0; i < len(grid2); i++ {
        for j := 0; j < len(grid2[0]); j++ {
            if grid2[i][j] == 1 {
                result++
                dfs(grid2, i, j)
            }
        }
    }
    return result
}

func dfs(grid [][]int, i, j int) {
    // 超出索引边界
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[0]) {
        return
    }
    // 已经是海水了
    if grid[i][j] == 0{
        return
    }
    // 将 (i, j) 变成海水
    grid[i][j] = 0
    // 淹没上下左右的陆地
    dfs(grid, i-1, j)
    dfs(grid, i+1, j)
    dfs(grid, i, j-1)
    dfs(grid, i, j+1)
}