岛屿数量

怎样从“grid 1/0 计数岛屿数量,例 3 个岛。”推导出 网格 DFS · 岛屿，并证明每次状态变化都不会漏掉答案？

中心结论：扫描每格,遇 1 且未访问则 DFS/BFS 沉岛 count++。

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

在本站主例中，grid 1/0 计数岛屿数量,例 3 个岛。

算法最终需要得到或观察：岛屿数 3。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 visited/沉岛、count。
3. 3转移每一步按照 扫描每格,遇 1 且未访问则 DFS/BFS 沉岛 count++。
4. 4收尾读取 岛屿数 3。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：visited/沉岛、count。

要求找出地图中的孤岛。孤岛的含义是四周被海水包围的岛。 这一题可以按照第 79 题的思路进行搜索，只要找到为 "1" 的岛以后，从这里开始搜索这周连通的陆地，也都标识上访问过。每次遇到新的 "1" 且没有访问过，就相当于遇到了新的岛屿了。

扫描每格,遇 1 且未访问则 DFS/BFS 沉岛 count++。

执行过程中持续维护：visited/沉岛、count。

正确性依赖以下不变量：每次 DFS 标记一整连通块。

面试时可以压缩为：双重循环找入口,DFS/BFS 沉岛避免重复;时间 O(mn),递归 DFS 最坏空间 O(mn)。

落到当前题，执行机制可以压缩为：扫描每格,遇 1 且未访问则 DFS/BFS 沉岛 count++。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入grid 1/0 计数岛屿数量,例 3 个岛。 因为：扫描每格,遇 1 且未访问则 DFS/BFS 沉岛 count++。
2. 2扫描网格,遇 '1' 启动 DFS双重循环找未访问陆地。 因为：每个连通块只计数一次。
3. 3该连通块已全部标记继续扫描。 因为：O(mn) 每个格最多访问一次。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5该连通块已全部标记继续扫描。 因为：O(mn) 每个格最多访问一次。
6. 6发现新岛屿,起点 (3,3)从该陆地 DFS 标记整块。 因为：沉岛避免重复计数。
7. 7岛屿总数 3网格扫描结束。 因为：DFS/BFS 连通分量计数。
8. 8收尾与复杂度岛屿数 3。 因为：时间 O(m·n) · 空间 O(m·n)。扫描每格,遇 1 且未访问则 DFS/BFS 沉岛 count++。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

var dir = [][]int{
	{-1, 0},
	{0, 1},
	{1, 0},
	{0, -1},
}

func numIslands(grid [][]byte) int {
	m := len(grid)
	if m == 0 {
		return 0
	}
	n := len(grid[0])
	if n == 0 {
		return 0
	}
	res, visited := 0, make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == '1' && !visited[i][j] {
				searchIslands(grid, &visited, i, j)
				res++
			}
		}
	}
	return res
}

func searchIslands(grid [][]byte, visited *[][]bool, x, y int) {
	(*visited)[x][y] = true
	for i := 0; i < 4; i++ {
		nx := x + dir[i][0]
		ny := y + dir[i][1]
		if isInBoard(grid, nx, ny) && !(*visited)[nx][ny] && grid[nx][ny] == '1' {
			searchIslands(grid, visited, nx, ny)
		}
	}
}

func isInBoard(board [][]byte, x, y int) bool {
	return x >= 0 && x < len(board) && y >= 0 && y < len(board[0])
}

func main() {
    // 1. 主例
    //    输入：mode="islands", grid=[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
    //    期望：岛屿数 3。
    //
    // 2. 失败 / 未命中
    //    检查：原地改 grid 只省 visited 数组,递归栈最坏仍 O(m·n),不是 O(1)。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC695 最大面积；LC130 被围
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意grid 1/0 计数岛屿数量,例 3 个岛。
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化扫描每格,遇 1 且未访问则 DFS/BFS 沉岛 count++。
4. 4证明每次 DFS 标记一整连通块。
5. 5复杂度时间 O(m·n)，空间 O(m·n)