BM57　岛屿数量¶

中等通过率 39.97%python3核心代码模式样例通过牛客 AC广度优先搜索(BFS)dfs

一句话

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

解题思路¶

这题考什么¶

「岛屿」就是四连通的极大陆地块，数岛屿等价于数连通分量。从任意一格陆地出发把它所在的整块都标记掉，能发起几次这样的出发，就有几个岛。

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

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

连通分量的一般框架见 BFS 广度优先搜索。

数据规模与复杂度¶

01 矩阵范围不超过 200200 = 4e4 格，时限「其他语言 2 秒」。每格最多入队一次、出队一次，四个方向各查一次，时间 O(nm)。空间是队列的峰值：规则矩形上同时在队的是一条对角波前，量级 O(min(n,m))，岸线曲折时会更宽，保守按 O(n*m) 计——4e4 个坐标对，内存毫无压力。

坑在哪¶

淹的时机必须是入队时，不能等出队再淹。出队才标记的话，同一格会被四个邻居分别推进队列，队列规模翻几倍，最坏还会退化成重复扩展；计数虽仍正确（外层扫到它时它已是 '0'），但白跑一趟。
用显式队列的 BFS，不用递归 DFS。矩阵可到 200*200，一整片全是陆地时递归深度会到 4e4，远超 Python 默认的 1000 层递归上限，直接 RecursionError；调高上限又会撞上 C 栈。
题面注明「存储的 01 数据其实是字符 '0'、'1'」，可样例里写的是数字 1。两种形式都可能喂进来，所以比较统一走 str(...) == "1"；只写 == 1 或只写 == "1"，遇上另一种形式时全盘判成海洋，答案恒为 0。
直接把访问过的陆地改写成 '0' 省掉了一份 visited 数组，代价是原地修改了入参矩阵。本题判题不复查入参，无妨；若调用方还要复用这张图，就得另开标记数组。

样例复核¶

示例 1 的矩阵里，(0,0) 出发淹掉左上角三格，(1,3) 出发淹掉右侧四格， (4,2) 出发淹掉底部三格，共发起三次出发，输出 3，与样例一致。

参考实现¶

solutions/nowcoder/BM57/sol.py
from collections import deque
from typing import List, Optional


class Solution:
    def solve(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        n, m = len(grid), len(grid[0])
        count = 0

        # 外层逐格扫描：属于旧岛的格子在被淹时已改成 '0'，因此不会被二次计数
        for i in range(n):
            for j in range(m):
                # 判题可能喂字符 '1' 也可能喂数字 1，统一转成字符串再比
                if str(grid[i][j]) != "1":
                    continue
                # 找到一个新岛屿的入口，先计数，再把整块连通陆地淹掉
                count += 1
                grid[i][j] = "0"
                q = deque([(i, j)])
                # 显式队列的 BFS：全是陆地时递归写法的深度会到 4e4，必然爆栈
                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 < n and 0 <= ny < m and str(grid[nx][ny]) == "1":
                            grid[nx][ny] = "0"    # 入队时就淹掉，避免同一格重复入队
                            q.append((nx, ny))
        return count

BM57 岛屿数量¶