Posted on 2022-12-20 14:48
Uriel 閱讀(52)
評論(0) 編輯 收藏 引用 所屬分類:
搜索 、
閑來無事重切Leet Code
給出每個房間內擁有的鑰匙（room[i], 一個list），每個鑰匙的數值j表示可以開第j個房間，房間0沒有上鎖，問是否有辦法進入所有房間，簡單DFS或BFS
速度一般，目前沒想到優化
DFS版
1 #841
2 #Runtime: 311 ms (Beats 5.61%)
3 #Memory: 42.3 MB (Beats 5.96%)
4
5 class Solution(object):
6 def canVisitAllRooms(self, rooms):
7 """
8 :type rooms: List[List[int]]
9 :rtype: bool
10 """
11 def DFS(vis, cnt, keys):
12 if cnt == len(rooms):
13 return True
14 for i in keys:
15 if i not in vis:
16 vis.add(i)
17 keys = keys.union(set(rooms[i]))
18 if DFS(vis, cnt + 1, keys):
19 return True
20 return False
21 return DFS(set([0]), 1, set(rooms[0]))
BFS版
1 #841
2 #Runtime: 119 ms (Beats 16.14%)
3 #Memory: 14.4 MB (Beats 9.12%)
4
5 class Solution(object):
6 def canVisitAllRooms(self, rooms):
7 """
8 :type rooms: List[List[int]]
9 :rtype: bool
10 """
11 q = deque([set(rooms[0])])
12 print(q)
13 vis = set([0])
14 while q:
15 keys = q.popleft()
16 for i in keys:
17 if i not in vis:
18 vis.add(i)
19 keys = keys.union(rooms[i])
20 q.append(keys)
21 return len(vis) == len(rooms)