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: 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.length <= 100
• A[i][j] == 0 or A[i][j] == 1

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

Solution：

def shortestBridge(self, A):
“””
:type A: List[List[int]]
:rtype: int
“””
m = len(A)
n = len(A)
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()
while stack:
i, j = stack.pop()
A[i][j] = -1
for d in direction:
x, y = i+d, j+d
if 0<=x<m and 0<=y<n:
if A[x][y] == 0:
elif A[x][y] == 1:

i ,j = first()
dfs(i, j)
step = 0

while boundary:
new = []
for i, j in boundary:
for dire in direction:
x, y = i+dire, j+dire
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