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
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