题目描述

在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）

现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。

返回必须翻转的 0 的最小数目。（可以保证答案至少是 1。）

样例

输入：[[0,1],[1,0]]
输出：1

输入：[[0,1,0],[0,0,0],[0,0,1]]
输出：2

输入：[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

算法

(bfs + 双端队列) $O(n^2)$

将原来的地图建成图，每个点都是一个节点，为1的点表示本身就是岛，不需要翻转，因此边权为0，为0的点需要翻转，因此边权为1，因此这道题本质上是一个边权只有01的图的最短路问题，就是求两个本来不是一个岛屿的1之间的最短路。边权只有01的最短路可以用bfs + 双端队列来做，遇到边权为0的节点就放在队尾，遇到边权为1的节点就放在队首，然后从队尾不断弹出节点即可。

时间复杂度

用visit数组标记访问过的点，保证每个点只被访问一次，时间复杂度为$O(n^2)$。

Python 代码

from collections import deque
class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        m, n = len(grid), len(grid[0])
        start_pos = None
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1: # 找到岛屿作为起点
                    start_pos = (i, j)
                    break
        direc = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        q = deque()
        q.append((start_pos[0], start_pos[1], 0))
        visit = [[False for j in range(n)] for i in range(m)]
        visit[start_pos[0]][start_pos[1]] = True
        res = 0
        flag = False # 标记是否找到了两个原本不连通的岛屿的最短路
        while len(q) > 0:
            x, y, step = q.popleft() # 从队尾弹出
            for d in direc:
                xt = x + d[0]
                yt = y + d[1]
                if xt >= 0 and xt < m and yt >= 0 and yt < n and visit[xt][yt] == False:
                    visit[xt][yt] = True
                    if grid[xt][yt] == 1: # grid的值为1，则边权为0，插入队尾
                        res = max(res, step)
                        if step > 0: # step > 0说明找到了与起点不连通的岛屿，返回答案即可
                            flag = True
                            break
                        q.appendleft((xt, yt, step))
                    else: # grid的值为0，则边权为1，插入队首
                        q.append((xt, yt, step + 1))
            if flag:
                break
        return res