Shortest Bridge

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[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外面一层所有值

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