HackMD
841.Keys and Rooms
tags: Medium,DFS,BFS,Graph
題目描述
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
範例
Example 1:
Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation:
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
Constraints:
n==rooms.length- 2 <=
n<= 1000 - 0 <=
rooms[i].length<= 1000 - 1 <=
sum(rooms[i].length)<= 3000 - 0 <=
rooms[i][j]< n - All the values of
rooms[i]are unique.
解答
C#
public class Solution {
public bool CanVisitAllRooms(IList<IList<int>> rooms) {
bool[] unlocked = new bool[rooms.Count];
unlocked[0] = true;
Stack<int> roomKeys = new();
roomKeys.Push(0);
while (roomKeys.Count > 0) {
int roomKey = roomKeys.Pop();
foreach(int key in rooms[roomKey]) {
if (!unlocked[key]) {
unlocked[key] = true;
roomKeys.Push(key);
}
}
}
return unlocked.All(unlock => unlock);
}
}
JimDec 20, 2022
Javascript
function canVisitAllRooms(rooms) {
const visited = new Array(rooms.length).fill(false);
const stack = [0];
while (stack.length) {
const current = stack.pop();
if (visited[current]) continue;
visited[current] = true;
stack.push(...rooms[current]);
}
for (let i = 0; i < rooms.length; i++) {
if (!visited[i]) return false;
}
return true;
}
用Set寫了一個，感覺比較簡潔，但不會比較快。
function canVisitAllRooms2(rooms) {
const stack = [0];
const visited = new Set();
while (stack.length) {
const current = stack.pop();
if (visited.has(current)) continue;
visited.add(current);
stack.push(...rooms[current]);
}
return visited.size === rooms.length;
}
MarsgoatDec 20, 2022
Python
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
self.keys = {0}
self.visited = set()
def dfs(idx):
for i in range(len(rooms)):
if i in self.keys and i not in self.visited:
if i != 0 and i == idx:
continue
self.visited.add(i)
for key in rooms[i]:
self.keys.add(key)
dfs(i + 1)
dfs(0)
return len(self.visited) == len(rooms)
KobeDec 20, 2022
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
keys = set()
keys.add(0)
room_done = set()
while len(keys-room_done) > 0:
for room in keys-room_done:
for key in rooms[room]:
keys.add(key)
room_done.add(room)
return len(room_done) == len(rooms)
gpDec 20, 2022
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
keys = [0]
used_key = set()
while len(keys) and len(used_key) != len(rooms):
current_key = keys.pop()
if current_key in used_key:
continue
keys = rooms[current_key] + keys
used_key.add(current_key)
#print(used_key)
if len(used_key) != len(rooms):
return False
return True
玉山Dec 21, 2022
