题目重点：针对题目强调的多岛变体，先标记每座岛，再同步扩张水域求连接任意两岛所需最少翻转。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版是 0/1 矩形网格、四邻接，岛屿为原始陆地连通分量；距离定义为最少把几个水格翻为陆地，使任意两座原始岛连通。
- 不足两岛返回 None；如果实际问题指 Manhattan 距离、八邻接或指定两岛，需要改定义与算法。
解题路线
- 先对所有原始 1 格做 flood fill，给每座岛不同 owner ID；所有陆地格同时作为距离 0 的 BFS 起点入队，不能只从扫描到的第一座岛扩张。
- 波前向水格扩张，首次到达水格时记录来源岛 owner 与需要翻转的水格数 distance。相邻格已有不同 owner 时，两个波前相接，候选桥长为两边 distance 之和。
- 多源 BFS 按距离层推进，水格第一次占有就是某座岛到它的最小翻转数；任意跨 owner 的边给一条合法连接，取最小候选即全局最短。
- 对 608 张不超过 3×3 的二值网格，以枚举每个水格翻转子集的独立参考模型核验；包含 0、1 与 3+ 座岛。
手动走一遍
一维图 [1,0,1,0,1] 有三座岛，最少翻一个水格即可接通任意相邻两岛，返回 1；不能只为第一座岛寻找某指定终点。二维格中波前在水格或相邻边相遇都要检查。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections import deque
def min_water_to_connect_any_two(grid: list[list[int]]) -> int | None:
"""Four-neighbor binary grid; flip minimum water cells to join any 2 islands."""
if not grid or not grid[0] or any(len(row) != len(grid[0]) for row in grid):
raise ValueError("grid must be a nonempty rectangle")
rows, cols = len(grid), len(grid[0])
if any(value not in (0, 1) for row in grid for value in row):
raise ValueError("grid must contain only 0/1")
def neighbors(r, c):
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols:
yield nr, nc
owner = [[-1] * cols for _ in range(rows)]
wave = deque()
island_count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1 or owner[r][c] != -1:
continue
owner[r][c] = island_count
stack = [(r, c)]
while stack:
cr, cc = stack.pop()
wave.append((cr, cc))
for nr, nc in neighbors(cr, cc):
if grid[nr][nc] == 1 and owner[nr][nc] == -1:
owner[nr][nc] = island_count
stack.append((nr, nc))
island_count += 1
if island_count < 2:
return None
distance = [[0] * cols for _ in range(rows)]
best = rows * cols
while wave:
r, c = wave.popleft()
if distance[r][c] >= best:
continue
for nr, nc in neighbors(r, c):
if owner[nr][nc] == -1:
owner[nr][nc] = owner[r][c]
distance[nr][nc] = distance[r][c] + 1
wave.append((nr, nc))
elif owner[nr][nc] != owner[r][c]:
best = min(best, distance[r][c] + distance[nr][nc])
return best
复杂度
标岛与多源 BFS 都最多访问每格常数次，时间 O(RC)，owner/distance/队列空间 O(RC)。若大图无法入内存，需要块/图压缩或外存方法，题目未明确此规模。
易错点与追问
容易失分的边界
- 按标准两岛题只扩张第一座岛，漏掉其它两座更近。
- 在陆地标岛时把对角线误当连通。
- 两个波前碰撞时多加一，误把两侧已有水格重复计算。
- 不足两岛时返回 0，和‘连接两座原始岛’不一致。
- 题目的‘距离’未定义就把翻水格数冒充唯一口径。
继续深挖
- 若要求连接所有岛，为什么两岛最短桥答案不够？
- 若水格翻转成本不同，BFS 如何改成 Dijkstra？
- 若按八邻接定义岛屿，标岛和扩张规则怎样变？
- 怎样返回实际要翻转的水格路径？
