题目重点：将已有岛预先编号，对每个0合并不同邻岛，避免同一岛重复计面积。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练二值矩形、4邻接，最多把一个0变1，求最大连通1面积；输入不改，空0。全部1允许不翻，全部0非空返回1。
- 这是largest island flip-one，不是“新增多个岛且不能邻接旧岛”的不同约束。
解题路线
- 一次DFS给每个旧岛componentId并存size，用独立labels保持grid不变。入stack就登记标号，避免同格多次入栈计数。
- 对每个0检查最多4邻居labels，先set去重，再candidate=1+sum(size[id])。0标签size0，不带贡献。
- 为什么足够？翻一个格后只有它相邻旧分量会被连起来，其他岛不受影响；不同邻岛完整面积可加，同岛从多个方向接触只算一次。
- best先取已有最大岛，覆盖全部1无0情况。枚举所有0保证最优翻点，不能贪心选最多1邻居数量，因为岛面积不同。
手动走一遍
[[1,1],[1,0]]最后0邻接上/左都属同岛，candidate1+3=4，不能算1+3+3=7。[[1,0],[0,1]]翻一个0可连两个单格岛得到3。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def largest_island(grid):
"""Four-neighbor binary grid, flip at most one 0; input unmodified."""
if not grid or not grid[0]:return 0
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('binary rectangle')
labels=[[0]*cols for _ in range(rows)];sizes={0:0};component=0
def adjacent(r,c):
for dr,dc in ((-1,0),(1,0),(0,-1),(0,1)):
rr,cc=r+dr,c+dc
if 0<=rr<rows and 0<=cc<cols:yield rr,cc
for r in range(rows):
for c in range(cols):
if grid[r][c]==0 or labels[r][c]:continue
component+=1;labels[r][c]=component;stack=[(r,c)];count=0
while stack:
rr,cc=stack.pop();count+=1
for nr,nc in adjacent(rr,cc):
if grid[nr][nc] and not labels[nr][nc]:labels[nr][nc]=component;stack.append((nr,nc))
sizes[component]=count
best=max(sizes.values())
for r in range(rows):
for c in range(cols):
if grid[r][c]==0:
neighbors={labels[rr][cc] for rr,cc in adjacent(r,c)}
best=max(best,1+sum(sizes[id] for id in neighbors))
return best
复杂度
O(RC)标号+O(RC)枚举，额外labels/size/stack O(RC)，每0邻居set最多4为常数。暴力每0重新floodfill最坏O((RC)²)。
易错点与追问
容易失分的边界
- 邻居不去重把同一岛重复计面积。
- 全部1时best初始化0后只枚举0，会错误返回0。
继续深挖
- 最多翻两个0为什么不能仅各自评分相加？二者可相连且共享旧岛。
- 允许8邻接时标号和翻点邻居集合都要一起改。
