LC 0934 [M] Shortest Bridge - ALawliet/algorithms GitHub Wiki
DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
class Solution:
def shortestBridge(self, A: List[List[int]]) -> int:
bounds = set()
n_rows, n_cols = len(A), len(A[0])
# get root of island 1
def getfirst():
for r in range(n_rows):
for c in range(n_cols):
if A[r][c] == 1:
return r, c
r, c = getfirst()
# get boundary of island 1
def dfs(r, c):
A[r][c] = -1 # mark visited
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < n_rows and 0 <= nc < n_cols:
if A[nr][nc] == 0:
bounds.add( (r, c) )
elif A[nr][nc] == 1: # flood fill/mark visited it the whole island 1
dfs(nr, nc)
dfs(r, c)
# BFS to find next island
steps = 0
Q = bounds
while Q:
Q_next = []
for r, c in Q:
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < n_rows and 0 <= nc < n_cols:
if A[nr][nc] == 1:
return steps
elif A[nr][nc] == 0:
A[nr][nc] = -1
Q_next.append( (nr, nc) )
steps += 1
Q = Q_next