力扣 934. 最短的桥

解法

from collections import deque
def shortestBridge(grid):
    n = len(grid)
    queue, island = deque(), set()
    # 第一次bfs查找第一个岛
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                queue.append((i, j, 0))
                island.add((i, j))
                break
        if queue:
            break
    
    # 第二次bfs查找扩展岛边界直到两岛接触
    while queue:
        x, y, step = queue.popleft()
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            cx, cy = x + dx, y + dy
            if 0 <= cx < n and 0 <= cy < n and (cx, cy) not in island:
                island.add((cx, cy))
                if grid[cx][cy] == 1:
                    if step:
                        return step
                    queue.appendleft((cx, cy, 0))
                else:
                    queue.append((cx, cy, step + 1))
    return 0