岛屿问题

一句话说明

岛屿题的本质是：在二维网格里找到一个连通块后，用 DFS 或 BFS 一次性把整块陆地“吃干净”，避免重复统计。

先想清楚 DFS 在做什么

• 遇到一块新的陆地，就说明发现了一个新岛屿。
• 从这个格子出发，把上下左右能连到的陆地全部访问掉。
• 整个连通块只会被统计一次。

1 1 0 0
1 0 0 1
0 0 1 1
 
从左上角开始 DFS：
第一块岛屿全部沉没后，只剩右下角那一大片

Go 代码：岛屿数量

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

为什么这种写法不会重复计数

关键不变量是：

• 外层循环只在遇到还没访问过的陆地时才 count++。
• 一旦进入 DFS，整块岛屿都会被改写成水域或访问态。
• 所以下次扫描到这块区域时，不会再次进入 DFS。

Go 代码：最大岛屿面积

这题只是把“计数岛屿个数”改成“返回这一整块连通块的大小”。

func maxAreaOfIsland(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }
 
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == 0 {
            return 0
        }
 
        grid[i][j] = 0
        return 1 + dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
    }
 
    best := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                if area := dfs(i, j); area > best {
                    best = area
                }
            }
        }
    }
 
    return best
}

Go 代码：岛屿周长

周长题不一定非要 DFS。更直接的想法是：

• 每块陆地先贡献 4 条边。
• 如果某个方向邻居也是陆地，那这一条边不算外边界。

func islandPerimeter(grid [][]int) int {
    if len(grid) == 0 {
        return 0
    }
 
    perimeter := 0
    directions := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
 
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] != 1 {
                continue
            }
 
            for _, d := range directions {
                ni, nj := i+d[0], j+d[1]
                if ni < 0 || ni >= len(grid) || nj < 0 || nj >= len(grid[0]) || grid[ni][nj] == 0 {
                    perimeter++
                }
            }
        }
    }
 
    return perimeter
}

Go 代码：DFS 版周长

如果题目要求你从“连通块递归”的角度理解，也可以这样写：

func islandPerimeterDFS(grid [][]int) int {
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == 0 {
            return 1
        }
        if grid[i][j] == -1 {
            return 0
        }
 
        grid[i][j] = -1
        return dfs(i+1, j) + dfs(i-1, j) + dfs(i, j+1) + dfs(i, j-1)
    }
 
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 1 {
                return dfs(i, j)
            }
        }
    }
 
    return 0
}

Go 代码：最大人工岛

这一题的关键不是直接暴力翻每个 0，而是先给每个岛屿编号：

1. 先把所有原始岛屿染成 2, 3, 4...
2. 记录每个编号对应的面积
3. 再枚举每个 0，看它四周连着哪些不同编号的岛屿

func largestIsland(grid [][]int) int {
    n := len(grid)
    islandID := 2
    areaMap := make(map[int]int)
 
    var dfs func(i, j, id int) int
    dfs = func(i, j, id int) int {
        if i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1 {
            return 0
        }
 
        grid[i][j] = id
        return 1 + dfs(i+1, j, id) + dfs(i-1, j, id) + dfs(i, j+1, id) + dfs(i, j-1, id)
    }
 
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                areaMap[islandID] = dfs(i, j, islandID)
                islandID++
            }
        }
    }
 
    best := 0
    for _, area := range areaMap {
        if area > best {
            best = area
        }
    }
 
    directions := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] != 0 {
                continue
            }
 
            seen := make(map[int]bool)
            area := 1
            for _, d := range directions {
                ni, nj := i+d[0], j+d[1]
                if ni >= 0 && ni < n && nj >= 0 && nj < n {
                    id := grid[ni][nj]
                    if id > 1 && !seen[id] {
                        seen[id] = true
                        area += areaMap[id]
                    }
                }
            }
            if area > best {
                best = area
            }
        }
    }
 
    if best == 0 {
        return 1
    }
    return best
}

四方向遍历写法

dfs(i+1, j)
dfs(i-1, j)
dfs(i, j+1)
dfs(i, j-1)

或者：

directions := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
for _, d := range directions {
    dfs(i+d[0], j+d[1])
}

易错点

• 岛屿题默认只看上下左右，不看对角线。
• 用修改原数组做访问标记时，别忘了这会破坏输入。
• 最大人工岛 里相邻岛屿编号要去重，否则会重复加面积。
• 递归深度很大时，Go 也可能因为深搜层数太深而变慢，这时可以改显式栈。

相关主题

• DFS基础模板
• BFS基础模板

---

返回：搜索算法