Posted on 2023-09-17 19:02
Uriel 閱讀(33)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給出一個有向圖每個節點的鏈接情況（graph[i]表示與節點i相連的節點），問最少走過多少跳變可以遍歷所有節點，BFS，用二進制mask記錄走過的節點，vis[bit_mask][node]=1記錄已經走過bit_mask中存儲的節點，并且最后剛剛經過node節點
1 #847
2 #Runtime: 76 ms (Beats 100%)
3 #Memory: 14.2 MB (Beats 87.50%)
4
5 class Solution(object):
6 def shortestPathLength(self, graph):
7 """
8 :type graph: List[List[int]]
9 :rtype: int
10 """
11 n = len(graph)
12 vis_mask = (1 << n) - 1
13 q = deque()
14 vis = [[0] * n for _ in range(vis_mask + 1)]
15 for x in xrange(n):
16 ini_mask = 1 << x
17 q.append((x, ini_mask, 1))
18 vis[ini_mask][x] = 1
19 while q:
20 t = q.popleft()
21 cur_node, cur_mask, cur_len = t
22 if cur_mask == vis_mask:
23 return cur_len - 1
24 for nei in graph[cur_node]:
25 new_mask = cur_mask | (1 << nei)
26 if vis[new_mask][nei]:
27 continue
28 q.append((nei, new_mask, cur_len + 1))
29 vis[new_mask][nei] = 1
30 return -1