Amazon Coding：最多翻一格 0，最大岛屿面积是多少？

题意与假设

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

• 训练0/1矩形四邻接，最多把一个0改1，不改也允许；不修改原grid。
• 空矩阵或零列返回0，全0非空返回1，全1返回总面积。

解题路线

1. 先DFS给每个现有岛唯一id并存area；每个0枚举四邻id去重，候选面积=1+Σ不同相邻岛area。
2. 翻0只会把它接触的分量连接起来，不可能影响其他岛；因此候选公式精确。枚举所有0及原有最大岛，覆盖最多一次修改所有选择。
3. 四个邻格可能属于同一岛，必须按id set去重，而不是逐方向加面积。0背景id的area设0，方便边界处理。
4. 示例复用已验证的Microsoft标准训练实现；来源与岗位各自独立，代码共享不说明两公司未公开正式细则相同。
5. 多次翻格不可对单次候选取最大的两个相加：两零可能共同建立新连接，问题需要新模型。

手动走一遍

训练[[1,1],[1,0]]，零的上/左都在同一个面积3的岛，只加一次得到4，不是7。[[1,0],[0,1]]翻任一零得到3。

Python 参考实现

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

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

"""Largest 4-neighbor island area after changing at most one zero to one."""


def largest_island_after_one_addition(grid: list[list[int]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    if any(len(row) != cols or any(value not in (0, 1) for value in row) for row in grid):
        raise ValueError("rectangular binary grid required")
    if cols == 0:
        return 0

    island_id = [[0] * cols for _ in range(rows)]
    area = {0: 0}
    next_id = 1
    for start_r in range(rows):
        for start_c in range(cols):
            if grid[start_r][start_c] == 0 or island_id[start_r][start_c] != 0:
                continue
            island_id[start_r][start_c] = next_id
            stack = [(start_r, start_c)]
            size = 0
            while stack:
                r, c = stack.pop()
                size += 1
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and island_id[nr][nc] == 0:
                        island_id[nr][nc] = next_id
                        stack.append((nr, nc))
            area[next_id] = size
            next_id += 1

    best = max(area.values())
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 0:
                continue
            neighbors = set()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    neighbors.add(island_id[nr][nc])
            best = max(best, 1 + sum(area[component] for component in neighbors))
    return best

复杂度

O(RC)时间与空间，每零最多核4个id；独立参考逐零修改再全图探索是小规模验证而非生产解。

易错点与追问

容易失分的边界

• 四邻同岛面积重复加。
• 没有0时返回0。
• 多次翻格直接独立相加。

继续深挖

• 翻格成本不同怎样加预算？
• 要返回翻哪个坐标？
• 对角也连通怎样调整邻居？