TikTok 岛屿数量：BFS 不修改 Grid，怎样覆盖每个分量？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练grid为矩形0/1二维数组，1为陆地，四邻接，不把对角相接合并。
• 独立seen集合保存已发现坐标，输入保持不变；空grid或零列返回0。
• 来源中未说明的变体按此标准合同训练，不由谐音编号猜测额外功能。

解题路线

1. 最大岛屿面积追问复用同一四邻接分量遍历，对每个分量统计cells数量后取最大，空网格/全海为0。代码largest_island_area使用已收集分量，保持不修改输入；若只需面积，可以不存全部cells而维护计数，仍需visited。
2. 从每个未见过的陆地开始BFS，一次遍历收集一个连通分量，分量数量就是岛屿数量。水格不是节点，不因为边界上出现水就提前结束外层扫描。
3. 在入队时标seen，而不是出队后标。多个邻居可能同时发现同一格，后标会重复入队并影响面积/内存；入队标记确保每个陆地只排队一次。
4. BFS只能走合法范围的四邻陆地；输入不改写意味着不能用grid值置零当visited。seen与队列的额外空间是必须在复杂度里承认的约束成本。
5. 正确性分两面：同一岛屿中任一点都有四邻路径，BFS会沿路径访问它；BFS不跨水因此不会合并不同岛屿。外层遇到每个未访问分量时恰好计一次。
6. 最大面积直接取每个收集分量的格数最大值，无陆地为0。面积与岛屿数量是两个输出，不要为了面积把已访问格再探索一遍。
7. 深蛇形岛屿用递归DFS可能超过语言栈限制，显式BFS/DFS栈更稳。广阔岛屿的BFS前沿仍可能很大，不应声称总是O(行宽)空间。
8. 只需数量时无需保留全部cells列表，示例为了复用形状追问保留分量坐标；可在每次BFS完成后只计数/取面积，减少中间保存但seen仍可O(RC)。

手动走一遍

[[1,0,1],[1,0,1]]有两个岛，每个面积2。[[1,0],[0,1]]按四邻域有两个岛；若改为八邻域则变一个，必须先核定。输入前后相同，单独访问记录不会写陆地值。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""0/1 rectangular grid, four neighbors, BFS without mutating input.
Shape equivalence: translation alone or translation + rotations/reflections.
"""
from collections import deque


def island_cells(grid):
    if not grid:
        return []
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols or any(v not in (0, 1) for v in row) for row in grid):
        raise ValueError('rectangular binary grid required')
    seen, components = set(), []
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1 or (r, c) in seen:
                continue
            seen.add((r, c))
            queue = deque([(r, c)])
            cells = []
            while queue:
                x, y = queue.popleft()
                cells.append((x, y))
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    a, b = x + dx, y + dy
                    if 0 <= a < rows and 0 <= b < cols and grid[a][b] == 1 and (a, b) not in seen:
                        seen.add((a, b))
                        queue.append((a, b))
            components.append(cells)
    return components


def normalize(cells):
    x0 = min(x for x, y in cells)
    y0 = min(y for x, y in cells)
    return tuple(sorted((x - x0, y - y0) for x, y in cells))


def distinct_island_shapes(grid, rotations_reflections=False):
    signatures = set()
    for cells in island_cells(grid):
        if not rotations_reflections:
            signatures.add(normalize(cells))
        else:
            variants = [[] for _ in range(8)]
            for x, y in cells:
                for target, point in zip(variants, ((x, y), (x, -y), (-x, y), (-x, -y),
                                                   (y, x), (y, -x), (-y, x), (-y, -x))):
                    target.append(point)
            signatures.add(min(normalize(v) for v in variants))
    return len(signatures)


def count_islands(grid):
    return len(island_cells(grid))


def largest_island_area(grid):
    return max((len(cells) for cells in island_cells(grid)), default=0)

复杂度

O(RC)时间，每格外层一次且陆地最多探索四条边；seen/队列/分量坐标O(RC)最坏空间。只计数可不保留全部坐标，但仍需访问记录。

易错点与追问

容易失分的边界

• 把对角边默认当邻接。
• 出队才标seen导致重复计面积。
• 要求不修改却把1置0。
• 只从左上角启动漏分量。

继续深挖

• 怎样同时返回最大面积？
• 输入逐行流式到来如何维护分量？
• 八邻域会改变哪些证明？
• 如何用并查集对照验证？