# Shortest Bridge

1 min readMar 11, 2021

--

In a given 2D binary array `A`

, there are two islands. (An island is a 4-directionally connected group of `1`

s not connected to any other 1s.)

Now, we may change `0`

s to `1`

s so as to connect the two islands together to form 1 island.

Return the smallest number of `0`

s that must be flipped. (It is guaranteed that the answer is at least 1.)

**Example 1:**

**Input:** A = [[0,1],[1,0]]

**Output:** 1

**Example 2:**

**Input:** A = [[0,1,0],[0,0,0],[0,0,1]]

**Output:** 2

**Example 3:**

**Input:** A = [[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

**Constraints:**

`2 <= A.length == A[0].length <= 100`

`A[i][j] == 0`

or`A[i][j] == 1`

思考：

- 先找到第一个island的点
- 从第一点dfs找到boundary的值
- bfs， check boundary的每一个值，+1能不能够到第二个island
- 如果不可以，那遍历boundary外面一层所有值

Solution：

`def shortestBridge(self, A):`

“””

:type A: List[List[int]]

:rtype: int

“””

m = len(A)

n = len(A[0])

boundary = set()

direction = [(0,1), (1,0), (-1, 0), (0, -1)]

def first():

for i in range(m):

for j in range(n):

if A[i][j] == 1:

return i, j

def dfs(i, j):

stack = set()

stack.add((i, j))

while stack:

i, j = stack.pop()

A[i][j] = -1

for d in direction:

x, y = i+d[0], j+d[1]

if 0<=x<m and 0<=y<n:

if A[x][y] == 0:

boundary.add((i,j))

elif A[x][y] == 1:

stack.add((x,y))

i ,j = first()

dfs(i, j)

step = 0

while boundary:

new = []

for i, j in boundary:

for dire in direction:

x, y = i+dire[0], j+dire[1]

if 0<=x<m and 0<=y<n:

if A[x][y] == 1:

return step

elif A[x][y] == 0:

A[x][y] = -1

new.append((x,y))

step += 1

boundary = new