0934._Shortest_Bridge.md

934. Shortest Bridge

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/shortest-bridge/

内容描述

In a given 2D binary array A, there are two islands.  (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped.  (It is guaranteed that the answer is at least 1.)

 

Example 1:

Input: [[0,1],[1,0]]
Output: 1
Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
Example 3:

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
 

Note:

1 <= A.length = A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

开始的想法是算出两个岛屿的所有点后，然后两两配对取其中最短距离，但比赛一直超时，看来2次travalse不行

参考haitao7哥的代码，不需要两次travalse，得到第一个岛屿后只需要继续往外延伸，每延伸一步step递增1， 首次返回的step为最短距离

beats 100%

class Solution(object):
    def shortestBridge(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        row = len(A)
        col = len(A[0]) if row else 0
        def getFirstIsland():
            visited, stack = {(i,j)}, [(i,j)]
            while stack:
                x, y = stack.pop()
                for m,n in [[x-1,y], [x+1,y], [x,y-1], [x,y+1]]:
                    if 0 <= m < row and 0 <= n < col:
                        if A[m][n] == 1 and (m,n) not in visited:
                            visited.add((m,n))
                            stack.append((m,n))
            return visited, stack
        
        for i in range(row):
            flag = False        
            for j in range(col):
                if A[i][j] == 1 and not flag:
                    island, stack = getFirstIsland()
                    flag = True
            if flag:
                break
                
        stack = [(x,y,0) for x,y in island]
        visited = {(i,j) for i, j in island}
        
        while stack:
            x, y, step = stack.pop()
            for m,n in [[x-1,y], [x+1,y], [x,y-1], [x,y+1]]:
                if 0 <= m < row and 0 <= n < col:
                    if A[m][n] and (m,n) not in island:
                        return step
                    if (m,n) not in visited:
                        stack.append((m,n,step+1))
                        visited.add((m,n))