岛屿数量

难度：⭐⭐⭐ 面试高频

考点

• DFS/BFS 矩阵搜索
• 连通分量计数
• 字节面试高频题

题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿被水包围，通过水平或垂直方向上相邻的陆地连接而成。

函数签名

func numIslands(grid [][]byte) int

示例

输入：
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

输入：
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

要求

1. 时间复杂度 O(m*n)

提示

• 遍历每个格子，遇到 '1' → 岛屿数+1，然后用 DFS/BFS 把整个岛标记为已访问
• 可以直接将 '1' 改为 '0' 表示已访问（原地修改，无需 visited 数组）
• DFS：四个方向递归
• BFS：队列 + 四方向扩展

---

参考答案（Go）

点击展开参考答案

//go:build ignore

package answer

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

func dfs(grid [][]byte, i, j, rows, cols int) {
	if i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] != '1' {
		return
	}
	grid[i][j] = '0'
	dfs(grid, i+1, j, rows, cols)
	dfs(grid, i-1, j, rows, cols)
	dfs(grid, i, j+1, rows, cols)
	dfs(grid, i, j-1, rows, cols)
}