-
Notifications
You must be signed in to change notification settings - Fork 5
/
21: 934. Shortest Bridge.py
47 lines (43 loc) · 1.55 KB
/
21: 934. Shortest Bridge.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# problem:
# https://leetcode.com/problems/shortest-bridge/
# solution:
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
N = len(grid)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def inbound(r, c):
return 0 <= r < N and 0 <= c < N
start = None
for i in range(N):
for j in range(N):
if grid[i][j]:
start = (i, j)
break
if start: break
def bfs(turn, queue):
count = -1
while queue:
M = len(queue)
count += 1
for _ in range(M):
r, c = queue.popleft()
if turn:
store.append((r,c))
for x, y in directions:
nr = x + r
nc = y + c
if inbound(nr, nc) and (nr, nc) not in visited:
if turn and grid[nr][nc]:
queue.append((nr, nc))
visited.add((nr, nc))
if not turn and grid[nr][nc]:
return count
if not turn and not grid[nr][nc]:
queue.append((nr, nc))
visited.add((nr, nc))
return count
visited = set()
visited.add((start))
store = deque([])
bfs(True,deque([start]))
return bfs(False, store)