岛屿数量
Number of Islands
在由 '1'（陆地）和 '0'（水）组成的网格里，数出上下左右相连的陆地一共有多少块。
在力扣中练习题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 输出：1
示例 2：
输入：grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
解题思路
DFS · 淹岛
发现一块陆地，就把和它连着的整片都改成水
一座岛由上下左右连通的陆地组成，不能把每个 1 都算成新岛。扫描到一个尚未访问的 1 时计数一次，再把与它连通的整片陆地全部标记掉。
自拟网格是 ["11000","01011","00110","10100"]，共有 3 座岛。它同时包含弯曲连通块、对角接触和一个孤立格，不能用“看起来挨着”代替四方向连通。
发现新的未访问陆地 (0,0)，岛数变为 1。
DFS 一进入陆地，先把它改为 0，再递归四个方向。图中的 ✓ 表示这个位置原本是陆地，现在已经沉为 0；原来的水用淡色 0 区分。
发现新的未访问陆地 (1,3)，岛数变为 2。
先标记再递归可以防止相邻格反复访问。整片沉完后继续扫描，只有下一个仍为 1 的位置才开启新岛，因而一座岛只计一次；对角线不在这四个递归方向中。
易错点
- 忘记把访问过的格子改成 '0'，DFS 会在两个格子之间反复递归，直到爆栈。
- 先递归再判界，或者只判断「不是水」而漏掉越界，都会直接数组越界。
- 300×300 全陆地时递归深度能到 9×10⁴ 层，有爆栈风险；不确定就换 BFS 或显式栈。
BFS · 队列扩散
用队列一层层把同一座岛吞掉，不怕递归太深
同样是 O(mn) 的正确遍历，队列代替递归栈，适合担心深递归时使用。
DFS 是「一条路走到黑」，BFS 是「一圈一圈往外扩」。两者都能把一座岛整片标记掉，区别只在访问顺序。
写法上有个容易踩的坑：入队时就标记，而不是出队时。如果等到出队才改成 '0'，同一个格子可能被多个邻居重复入队，队列会膨胀好几倍。
BFS 的好处是不会爆栈——递归的深度取决于岛屿的蛇形长度，而 BFS 只用一个队列，宽度取决于岛的「周长」，跟递归深度无关。
时间复杂度一样是 O(m·n)：每个格子入队一次、出队一次。空间是队列的大小，最坏 O(m·n)。
如果题目要的是「最短几步能到」，也必须用 BFS——层数就是步数，这是 DFS 给不了的性质。
- 1扫描网格，遇到 '1' 就岛屿数 +1。
- 2把该格子标记为 '0' 并压入队列。
- 3不断弹出队首，检查四个邻居：在界内且是 '1' 就标记后入队。
- 4队列空了，这一座岛就处理完，回到外层继续扫描。
易错点
- 出队时才标记：同一格会被多个邻居重复入队，队列膨胀。
- 四个方向里漏方向，或者把行列写反（grid[x][y] 与 grid[y][x]）。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
grid = ["11000","01011","00110","10100"]逐行扫描，只在遇到尚未访问的 1 时新增一座岛。对角接触不算连通。
查看 C++ 代码
延伸阅读
- 把原数组直接当 visited 用，是最省空间的写法；如果输入不允许修改，就另外开一个 visited。
- 同一个模板能做 695（最大岛屿面积）、130（被围绕的区域）、417（太平洋大西洋水流），只是「扩散条件」不同。
- 只问连通块个数时，并查集也能做：把相邻的陆地 union 起来，最后数一数有几个根。