934 Shortest Bridge

link: Shortest Bridge

Thought

Since the question ask for shortest, so BFS probabely the best algorithms to solve it. But notice, I will use 2 bfs funciton, one to find the edge of first island, the other one is to reach another island based on first edge.

BFS1:

input: start position
stop condition: queue empty
generate & expansion rule: find all its neighbors, mark as visited, and put ‘1’ to queue -> will put that node in queue for further processing.
put ‘0’ to result queue ->thats what we want to return!

BFS2

input: edge of first island
stop condition: reach any grid with number ‘1’ -> find second island
generate & expansion rule: for any node in que, expend its unvisited neighbors in queue. And also record the level number.

Code

class Solution:
    def shortestBridge(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        delta = ((0,1), (1,0), (0,-1), (-1,0))
        N = len(A)
        visited = set()
        def bfs1(x,y):
            # get the edge of first one
            visited.add((x,y))
            que = collections.deque()
            que.append((x,y))
            result = collections.deque()
            while que:
                c_x,c_y = que.popleft()
                if A[c_x][c_y] == 0:
                    result.append((c_x,c_y))
                    continue
                for dx,dy in delta:
                    nx,ny = dx+c_x, dy+c_y
                    if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:
                        que.append((nx,ny))
                        visited.add((nx,ny))
            return result
        def bfs2(starts):
            cnt = 0
            while starts:
                siz = len(starts)
                for i in range(siz):
                    c_x,c_y = starts.popleft()
                    if A[c_x][c_y] == 1:
                        return cnt
                    for dx,dy in delta:
                        nx,ny = dx+c_x, dy+c_y
                        if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:
                            starts.append((nx,ny))
                            visited.add((nx,ny))
                cnt += 1
        for i in range(N):
            for j in range(N):
                if A[i][j] == 1: # find start position 
                    t = bfs1(i,j) # get the edge
                    return bfs2(t) # get level number

Runtime

Time: O(n^2)
Space: O(n^2)