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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store