算法1

DFS+BFS

Python 代码

    def shortestBridge(self, A: List[List[int]]) -> int:
        # DFS找到第一个岛，将第一个岛的数字变为2
        # BFS找第一个岛到第二岛的最短路径，layers即为最短路径
        directions = [[1,0],[-1,0],[0,1],[0,-1]]
        row = len(A)
        column = len(A[0])
        # 遍历地图，第一个岛标志为2，并用Q记录岛屿位置。使用DFS 递归法
        def DFS(i,j):
            if i not in range(row) or j not in range(column) or A[i][j] == 2:
                return
            if A[i][j] == 1:
                A[i][j] = 2
                Q.append((i,j))
                for direction in directions:
                    x = i+direction[0]
                    y = j+direction[1]
                    DFS(x,y)

        def BFS():
            # 从找到的岛开始扩展，每扩展一层，layer+1
            layer = 0
            while Q:
                size = len(Q) # 一圈一圈展开
                for _ in range(size):
                    tmp = Q.popleft()
                    i = tmp[0]
                    j = tmp[1]
                    for direction in directions:
                        x = i+direction[0]
                        y = j+direction[1]
                        if x not in range(row) or y not in range(column) or A[x][y] == 2:
                            continue
                        if A[x][y] == 1:
                            return layer
                        A[x][y] = 2 # 0标记为2，相当于剪枝，避免重复操作
                        Q.append((x,y))
                layer +=1

        # 第一步：通过DFS找到岛屿1的位置，将其标记为2，在DFS出栈的过程中，记下等于0的节点位置，即为岛屿最内圈的0的位置
        Q = collections.deque()
        for i in range(row):
            for j in range(column):
                if A[i][j] == 1:
                    # 找到第一个等于1的节点：
                    DFS(i,j)
                    # break
                    # 第二步，
                    return BFS()