Leetcode 934. Shortest Bridge (Python)

Related Topic

Breadth-First-Search. Depth-First-Search.

Description

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.)

Sample I/O

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

Methodology

Use DFS to find the first island and turn all 1s of first island to 2. Use BFS to expand the first island’s border by turning all adjacent 0 to 2. Add 1 step after the border expand 1 unit until the island 1 touched island2.

Code(DFS+BFS)

def shortestBridge(self, A: List[List[int]]) -> int:
        row,col = len(A),len(A[0])
        dirs = [(0,0),(-1,0),(0,-1),(1,0),(0,1)]
        island1 = collections.deque()
        def dfs(x,y):
            for dx, dy in dirs:
                if 0<=x+dx<row and 0<=y+dy<col and A[x+dx][y+dy]==1:
                    A[x+dx][y+dy]=2
                    island1.append([x+dx,y+dy])
                    dfs(x+dx,y+dy)
        #DFS Find the first island and turn all 1 to 2
        def findIsland1():
            for x in range(row):
                for y in range(col):
                    if A[x][y]:
                        return dfs(x,y)
        findIsland1()
        #BFS Expand the island and count step
        step = 0
        while island1:
            for _ in range(len(island1)):
                x,y=island1.popleft()
                for dx,dy in dirs:
                    nx,ny = x+dx, y+dy
                    if 0<=nx<row and 0<=ny<col and A[nx][ny]!=2:
                        if A[nx][ny] == 0:
                            A[nx][ny]=2
                            island1.append([nx,ny])
                        elif A[nx][ny] == 1:
                            return step
            step+=1
        return step

BigO

We traversal all elements of the 2D roughly twice so time complexity is roughly O(2mn) where m is row size and n is column size which is O(mn)