# Shortest Bridge

`Input: A = [[0,1],[1,0]]Output: 1`
`Input: A = [[0,1,0],[0,0,0],[0,0,1]]Output: 2`
`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`
• `2 <= A.length == A[0].length <= 100`
• `A[i][j] == 0` or `A[i][j] == 1`
1. 先找到第一个island的点
2. 从第一点dfs找到boundary的值
3. bfs， check boundary的每一个值，+1能不能够到第二个island
4. 如果不可以，那遍历boundary外面一层所有值
`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`

--

--

--

## More from Newbie Developer

Love podcasts or audiobooks? Learn on the go with our new app.