934 Shortest Bridge
link: Shortest Bridge
Thought
Since the question ask for shortest, so BFS probabely the best algorithms to solve it. But notice, I will use 2 bfs funciton, one to find the edge of first island, the other one is to reach another island based on first edge.
BFS1:
input: start position
stop condition: queue empty
generate & expansion rule: find all its neighbors, mark as visited, and put '1' to queue -> will put that node in queue for further processing.
put '0' to result queue ->thats what we want to return!
BFS2
input: edge of first island
stop condition: reach any grid with number '1' -> find second island
generate & expansion rule: for any node in que, expend its unvisited neighbors in queue. And also record the level number.
Code
class Solution:
def shortestBridge(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
delta = ((0,1), (1,0), (0,-1), (-1,0))
N = len(A)
visited = set()
def bfs1(x,y):
# get the edge of first one
visited.add((x,y))
que = collections.deque()
que.append((x,y))
result = collections.deque()
while que:
c_x,c_y = que.popleft()
if A[c_x][c_y] == 0:
result.append((c_x,c_y))
continue
for dx,dy in delta:
nx,ny = dx+c_x, dy+c_y
if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:
que.append((nx,ny))
visited.add((nx,ny))
return result
def bfs2(starts):
cnt = 0
while starts:
siz = len(starts)
for i in range(siz):
c_x,c_y = starts.popleft()
if A[c_x][c_y] == 1:
return cnt
for dx,dy in delta:
nx,ny = dx+c_x, dy+c_y
if 0 <= nx <N and 0 <= ny < N and (nx,ny) not in visited:
starts.append((nx,ny))
visited.add((nx,ny))
cnt += 1
for i in range(N):
for j in range(N):
if A[i][j] == 1: # find start position
t = bfs1(i,j) # get the edge
return bfs2(t) # get level numberRuntime
Time: O(n^2)
Space: O(n^2)
