岛屿系列题目的核心考点就是用 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)
}
网友评论