# Shortest Bridge

Shortest Bridge

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.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() stack.add((i, j)) 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: 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, 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`