> ## Content Index
> Fetch the complete content index at: https://andybase.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 934 Shortest Bridge
- URL: https://andybase.com/934-shortest-bridge/
- Published: 2018-11-08T16:36:11.000Z
- Updated: 2018-11-08T16:36:11.000Z
- Author: andy
- Tags: leetcode, contest, #Migrated-1784083136856, #wp, #wp-post, #Import 2026-07-15 02:38

link: [Shortest Bridge](https://leetcode.com/problems/shortest-bridge/?ref=andybase.com)

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