Posted on 2023-09-17 19:02
Uriel 阅读(25)
评论(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