[Leetcode 200] 岛屿数量

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

• grid[i][j] 的值为 '0' 或 '1'

解法一：DFS

• '1' 是陆地节点

• '0' 是水，不连通

• 一旦看到一个还没被处理过的 '1'，就说明发现了一座新岛，答案先 +1。

• 然后从这个格子出发，往四个方向（上、下、左、右）递归 dfs 把能连到的陆地都“染掉”。

• 染色的方式很简单粗暴：直接把 '1' 改成 '0'，表示“已经访问过 / 已经淹掉”。

• 时间：O(m·n)，每个格子最多被访问一次。

• 空间：最坏 O(m·n)（递归栈深度）。

解法二：BFS (推荐)

• 扫描网格，遇到 '1' 就说明发现新岛，结果 +1。

• 把这个格子加进队列，然后开始做 BFS：
• 从队列中弹出一个格子，把它视为当前“水淹到的地方”；
• 看它四个方向有没有 '1'，有的话就入队，并立刻改成 '0' 标记成“访问过”。

• 队列空了，说明这块岛全部处理完了，然后继续扫网格，找下一块岛。

• 时间：O(m·n)，每个格子也最多入队 / 出队一次。

• 空间：O(m·n)，最坏情况下队列里会装下整块大岛的一大部分。

解法三：并查集（Union-Find，“把陆地分组”）

1. 把每个陆地格子 (i, j) 看成一个节点，给它一个编号，比如 id = i * cols + j。

2. 遍历网格，当我们看到一个 '1' 时，就看它上面和左边（已经处理过的方向）是不是 '1'：
• 是的话，就把它们做一次 union，表示“这两个格子属于同一座岛”。
• 之所以只看上和左，是因为右和下会在将来的遍历里遇到，不需要重复连。

3. 所有 union 完毕后，我们再扫一遍所有 '1'，把它们的“根节点”找出来，根的不同个数就是岛的个数。

• 时间：O(m·n) 遍历一次网格 + 若干次 union / find
平均近似 O(m·n · α(mn))，其中 α 是反 Ackermann 函数，极慢，可以认为接近常数，所以几乎是O(m·n)。

• 空间：O(m·n)，需要为每个陆地格子维护一个并查集节点（parent 映射）。