求岛屿数量。

核心回答

把陆地格子看作图的节点，上下左右相邻的陆地之间有边，岛屿数量就是陆地连通分量的数量。

遍历整个网格，每遇到一块尚未访问的陆地，就将岛屿数加一，并用 BFS 或 DFS 标记与它连通的全部陆地。后续扫描再遇到这些格子时直接跳过，因此每座岛只计数一次。

下面采用迭代 BFS，避免大岛屿造成递归调用过深。对于 m 行 n 列网格，时间复杂度为 O(mn)，使用访问数组和队列时，额外空间复杂度为 O(mn)。

输入约定与例子

按力扣 200 的常见约定，输入是矩形字符网格，'1' 表示陆地，'0' 表示水。只计算上下左右四邻接，对角线相接不算连通；位于网格边缘的陆地仍然可以构成岛屿。以下实现还将空网格、零列网格的结果定义为 0。

例如：

1 1 0 0 1
1 0 0 0 1
0 0 1 0 0

左上角、右侧和底部中间分别形成一座岛，结果为 3。注意底部的单格不能因为与其他陆地“看起来很近”就并入同一座岛，必须存在四邻接的陆地路径。

Python 实现：迭代 BFS

这版使用独立的 visited，保留原网格内容。

from collections import deque


def num_islands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    islands = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != "1" or visited[r][c]:
                continue

            islands += 1
            visited[r][c] = True
            queue = deque([(r, c)])

            while queue:
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if (
                        0 <= nx < rows
                        and 0 <= ny < cols
                        and grid[nx][ny] == "1"
                        and not visited[nx][ny]
                    ):
                        visited[nx][ny] = True
                        queue.append((nx, ny))

    return islands

调用示例：

grid = [list("11001"), list("10001"), list("00100")]
print(num_islands(grid))  # 3

如果输入使用整数 1、0，将判断中的 "1" 改为 1，不要把字符与整数混用。实现按矩形网格约定访问；不规则行长度需要另行定义输入规则。

为什么在入队时标记

一个格子可能被多个相邻格子发现。如果等到出队才标记，它尚在队列中时，其他邻居还会把它再次加入。这里在首次发现并入队时就设置 visited，保证每块陆地最多入队一次。

Python 使用 deque.popleft() 取队首，避免 list.pop(0) 搬移后续元素。队列不设置 maxlen，否则容量满时可能丢弃尚未处理的格子。

正确性与复杂度

一次 BFS 从陆地出发，只沿相邻陆地扩展，因此不会跨水域走到另一座岛；另一方面，凡是与起点存在陆地路径的格子，都会随着路径上的节点被依次发现。所以这次搜索恰好标记起点所在的一整座岛。

扫描时，已统计岛屿的全部陆地都已标记，不能再次触发计数；未统计的岛屿至少有一个格子会被扫描到，并触发一次搜索。因此计数既不重复，也不遗漏。

外层扫描检查 mn 个格子。每块陆地最多入队、出队一次，最多检查四个方向，因此总时间为 O(mn)，不是“外层遍历 × 每次搜索整张图”。

visited 占 O(mn)；队列最坏也可用 O(mn) 作为上界，合计额外空间为 O(mn)。迭代遍历避免的是递归深度限制，并不意味着不需要存储待访问节点。

可以修改原图时怎样处理

如果允许改变输入，可以在发现陆地时直接将 '1' 改成 '0'，利用原网格记录访问状态，省去独立 visited。修改同样要在首次入队时完成。

这种方式会破坏原始数据，调用方后续再读取网格时看到的是修改后的结果。如果先复制网格再修改，复制本身仍需要 O(mn) 空间；即使直接修改原图，BFS 队列也有额外空间，不能将整套解法写成 O(1)。

常见追问

怎样改成迭代 DFS？

将 queue = deque([(r, c)]) 改为 queue = [(r, c)]，将 queue.popleft() 改为 queue.pop()，其余“发现即标记、加入待访问容器”的逻辑保持不变，就变成显式栈遍历。求连通分量不依赖按层顺序，因此两者得到相同计数。

如果斜对角也算连通呢？

把方向数组扩展为八个方向，加入四个对角方向。计数和标记机制不变。例如只有左上、右下两块陆地的 2×2 网格，四邻接答案为 2，八邻接答案为 1。

能否只扫描每格的左边和上边来直接计数？

只根据是否存在左、上陆地决定加一，可能把之后连起来的区域重复计数。如果采用并查集，则可以只检查左、上两条已经出现的边，但需要真正合并不同集合并维护连通分量数。单次静态计数通常用 BFS 或 DFS 更直接。

参考资料