LC200　岛屿数量¶

中等通过率 64.1%python3核心代码模式图论样例通过牛客 AC深度优先搜索广度优先搜索并查集数组矩阵

一句话

逐格扫描，遇到没访问过的陆地就把整片淹掉，淹的次数就是岛屿数。

解题思路¶

这题考什么¶

「岛屿」是四连通的极大陆地块，数岛屿等价于数无向图的连通分量个数。把每个 '1' 看成一个点、上下左右相邻的两个 '1' 之间连一条边，从任一格陆地出发把它所在的整块都标记掉，能发起几次这样的出发就有几个岛。

1 1 0 0 0        A A . . .
1 1 0 0 0        A A . . .
0 0 1 0 0   ->   . . B . .     发起三次出发 -> 3
0 0 0 1 1        . . . C C

扫描顺序保证不重不漏：外层双重循环遍历每一格，只有「当前是陆地且尚未被淹」才计数加一，随后把整块连通区域淹成海洋。已经归属某个岛的格子在被淹时就写成了 '0'，外层再走到它时不会二次计数。

连通分量与网格 BFS（广度优先搜索）的通用框架见 BFS 广度优先搜索。

数据规模与复杂度¶

1 <= m, n <= 300，最多 9e4 格。每格最多入队一次、出队一次，出队时查四个方向，时间 O(mn)，约 9e4 次基本操作。空间是队列峰值：整张图全是陆地时，同时在队的是一条对角波前，量级 O(m+n)；保守按 O(mn) 估也只有 9e4 个坐标对，内存毫无压力。

坑在哪¶

用显式队列的 BFS，不要写递归 DFS（深度优先搜索）。300*300 全是陆地时递归深度会到 9e4，远超 CPython 默认的 1000 层递归上限，直接 RecursionError；调高 sys.setrecursionlimit 又会撞上 C 栈，进程整个崩掉而不是报异常。
淹的时机必须在入队时，不能等出队再淹。出队才标记的话，同一格会被它的四个邻居分别推进队列，队列规模成倍膨胀；计数仍然正确（外层扫到它时已是 '0'），但白跑一趟，稠密陆地上退化成大量重复扩展。
网格里存的是字符 '1' / '0'，不是整数 1 / 0。写成 grid[i][j] == 1 恒为假，整张图都会被当成海洋，答案永远返回 0。
判边界必须在取值之前。Python 的负下标会绕回去读到对侧的格子，漏掉 0 <= nx 这一半条件时，第 0 行的上邻居会读成最后一行，把不相连的两块并成一岛。
把访问过的陆地直接改写成 '0'，省掉了一份 visited 数组，代价是原地修改了入参矩阵。本题判题只看返回值，无妨；若调用方之后还要复用这张图，就得另开标记数组。

样例复核¶

示例 2 的 4*5 矩阵：(0,0) 出发淹掉左上四格，(2,2) 出发淹掉中间一格， (3,3) 出发淹掉右下两格，共发起三次出发，输出 3，与样例一致。

参考实现¶

solutions/leetcode/LC200/sol.py
from collections import deque
from typing import List, Optional


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 题面保证 m, n >= 1，仍防一手空网格，免得 len(grid[0]) 直接下标越界
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0

        # 外层逐格扫描：属于旧岛的格子在被淹时已改成 '0'，因此不会被二次计数
        for i in range(m):
            for j in range(n):
                # 网格存的是字符，写成 == 1 会恒为假
                if grid[i][j] != "1":
                    continue
                # 找到一个新岛屿的入口：先记一笔，再把它所在的整块连通陆地淹掉
                count += 1
                grid[i][j] = "0"
                q = deque([(i, j)])
                # 显式队列的 BFS：全是陆地时递归写法深度会到 9e4，必然爆栈
                while q:
                    x, y = q.popleft()
                    for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                        # 先判边界再取值：负下标会绕回对侧，把不相连的两块并成一岛
                        if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
                            # 入队即淹，避免同一格被四个邻居重复推进队列
                            grid[nx][ny] = "0"
                            q.append((nx, ny))
        return count

LC200 岛屿数量¶