题目重点：给已有岛屿标号与面积，再枚举每个水格，合并最多四个不同相邻岛，避免同一岛重复计数。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- grid 为矩形 0/1 网格，1 是陆地，按上下左右四邻接。
- 最多把一格 0 改为 1；全陆地时无需改动并返回整片面积。若必须恰好翻一格，全陆地的输入应另定义无解。
- 返回最大连通岛屿的格子数，不返回翻转位置；空网格训练版返回 0。
解题路线
- 第一遍只访问原有陆地：对每个未标记的 1 用 DFS/BFS 赋唯一 componentId，记录 area[id]。每格恰好入栈一次。
- 第二遍枚举每个 0：收集四邻陆地的不同 id，候选面积为 1+这些 id 的面积之和。对同一岛出现的两条边只能加一次。
- 答案取原有最大面积和所有候选的最大值；原有最大值处理全陆地，也覆盖‘最多翻一格’语义。正确性来自任何一次翻转只可能连接与该水格四邻的旧岛，其余岛保持不变。
- 若要求一串动态 add 操作后持续返回最大面积，则应改用并查集增量维护；本题是一格一次性选择，组件标号更直接。
手动走一遍
[[1,0,1],[1,0,1]] 两列原岛面积分别 2、2。翻中间任一水格时连接两个不同 id，得到 1+2+2=5；若中间水格的上下左右有两格属于同一岛，id 集合保证面积只加一次。
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
复杂度
R×C 网格：两遍各 O(RC) 时间；标号矩阵、DFS 栈与面积表合计 O(RC) 空间。每个水格最多查看四邻，常数级去重。
易错点与追问
容易失分的边界
- 每尝试一个水格就全图重算，退化 O((RC)²)。
- 同一旧岛从两个方向邻接时累加两次面积。
- 对原输入就地翻转而未还原，后续候选受污染。
- 把对角线也算邻接却没写明。
- 全陆地返回 0 而不是当前面积。
继续深挖
- 若最多可翻两格，为什么简单取两个单格收益之和不正确？
- 若动态逐个加陆地并每步报告岛屿数及最大面积，怎样用并查集？
- 返回最优翻转坐标时并列如何定义？
