934. 最短的桥(Medium)

题目描述

在给定的二维二进制数组 A 中，存在两座岛。（0 表示海水， 1表示陆地），问最少需要多少桥可以连通两座岛。（可以保证答案至少是 1）

示例

Input：
[[0,1,0],
 [0,0,0],
 [0,0,1]]
Output：2

Input：
[[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]]
Output：1

题解

DFS + BFS 结合考题

由于无法区分两座小岛，首先需要使用搜索算法(一般使用DFS) 遍历小岛，将选定的小岛标记为2，然后使用 BFS 算法找出最少走几步（step）能到另外一座小岛。

因为是求最小值，所以建议使用 BFS算法。

Python示例

from collections import deque 
def dfs(A, r, c, island):
    island.append((r, c))
    A[r][c] =  2  # 选个小岛标记为 2
    for d in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        i = r + d[0]
        j = c + d[1]
        if 0 <= i < len(A) and 0 <= j < len(A[0]) and A[i][j] == 1:
            dfs(A, i, j, island)

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        island = deque()
        first = True 
        for i in range(len(A)):
            for j in range(len(A[0])):
                if not first: break # 只找一个岛
                if A[i][j] == 1:
                    dfs(A, i, j, island)   
                    first = False 

        step = 0
        while island:
            step += 1
            for _ in range(len(island)): # 同一层
                r, c = island.popleft()
                for d in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    i = r + d[0]
                    j = c + d[1]
                    if 0 <= i < len(A) and 0 <= j < len(A[0]) and A[i][j] != 2:
                        if A[i][j] == 1: 
                            return step - 1
                        else:
                            island.append((i, j))
                            A[i][j] = 2