https://leetcode.com/problems/keys-and-rooms/
https://leetcode.com/problems/keys-and-rooms/discuss/133895/Clean-Code
https://leetcode.com/problems/keys-and-rooms/discuss/135306/BFS-(9-lines-10ms)-and-DFS-(7-lines-18ms)-in-C%2B%2B-w-beginner-friendly-explanation
X. BFS
https://leetcode.com/problems/keys-and-rooms/discuss/200749/Java-DFS-BFS-solution-with-explanation
There are
N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.
Formally, each room
i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.
Initially, all the rooms start locked (except for room
0).
You can walk back and forth between rooms freely.
Return
true if and only if you can enter every room.
Example 1:
Input: [[1],[2],[3],[]] Output: true Explanation: We start in room 0, and pick up key 1. We then go to room 1, and pick up key 2. We then go to room 2, and pick up key 3. We then go to room 3. Since we were able to go to every room, we return true.
Example 2:
Input: [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can't enter the room with number 2.
Note:
1 <= rooms.length <= 10000 <= rooms[i].length <= 1000- The number of keys in all rooms combined is at most
3000.
When visiting a room for the first time, look at all the keys in that room. For any key that hasn't been used yet, add it to the todo list (
stack) for it to be used.
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] seen = new boolean[rooms.size()];
seen[0] = true;
Stack<Integer> stack = new Stack();
stack.push(0);
// At the beginning, we have a todo list "stack" of keys to use.
// 'seen' represents at some point we have entered this room.
while (!stack.isEmpty()) { // While we have keys...
int node = stack.pop(); // Get the next key 'node'
for (int nei : rooms.get(node)) // For every key in room # 'node'...
if (!seen[nei]) { // ...that hasn't been used yet
seen[nei] = true; // mark that we've entered the room
stack.push(nei); // add the key to the todo list
}
}
for (boolean v : seen) // if any room hasn't been visited, return false
if (!v)
return false;
return true;
}
https://leetcode.com/problems/keys-and-rooms/discuss/133855/Straight-Forward public boolean canVisitAllRooms(List<List<Integer>> rooms) {
Stack<Integer> dfs = new Stack<>(); dfs.add(0);
HashSet<Integer> seen = new HashSet<Integer>(); seen.add(0);
while (!dfs.isEmpty()) {
int i = dfs.pop();
for (int j : rooms.get(i))
if (!seen.contains(j)) {
dfs.add(j);
seen.add(j);
if (rooms.size() == seen.size()) return true;
}
}
return rooms.size() == seen.size();
}https://leetcode.com/problems/keys-and-rooms/discuss/133895/Clean-Code
https://leetcode.com/problems/keys-and-rooms/discuss/135306/BFS-(9-lines-10ms)-and-DFS-(7-lines-18ms)-in-C%2B%2B-w-beginner-friendly-explanation
We use an unordered_set to record the rooms visited, and a queue for BFS. Push room 0 to queue first.
While the queue is not empty, meaning we have more rooms to visit, we check all keys in the current room, if we haven't visit all of these rooms, push it to the queue.
While the queue is not empty, meaning we have more rooms to visit, we check all keys in the current room, if we haven't visit all of these rooms, push it to the queue.
bool canVisitAllRooms(vector<vector<int>>& rooms) {
unordered_set<int> visited;
queue<int> to_visit;
to_visit.push(0);
while(!to_visit.empty()) {
int curr = to_visit.front();
to_visit.pop();
visited.insert(curr);
for (int k : rooms[curr]) if (visited.find(k) == visited.end()) to_visit.push(k);
}
return visited.size() == rooms.size();
}
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] seen = new boolean[rooms.size()];
seen[0] = true;
Stack<Integer> stack = new Stack();
stack.push(0);
// At the beginning, we have a todo list "stack" of keys to use.
// 'seen' represents at some point we have entered this room.
while (!stack.isEmpty()) { // While we have keys...
int node = stack.pop(); // Get the next key 'node'
for (int nei : rooms.get(node)) // For every key in room # 'node'...
if (!seen[nei]) { // ...that hasn't been used yet
seen[nei] = true; // mark that we've entered the room
stack.push(nei); // add the key to the todo list
}
}
for (boolean v : seen) // if any room hasn't been visited, return false
if (!v)
return false;
return true;
}
https://leetcode.com/problems/keys-and-rooms/discuss/200749/Java-DFS-BFS-solution-with-explanation
Recursive DFS:
Use a set to track rooms that have been visited.
Starting from room 0, add 0 to the visited set, for each key in room 0,
if the key is not visited yet, add the key to visited and recursively visit keys in that room,
otherwise do not visit the room again.
We can visit all rooms only when the size of visited set equals to the size of the rooms.
Iterative BFS:
Use a queue to keep the keys we found in a room, only enqueue the keys not visited yet.
Repeat until the queue is empty, and check if size of visited set equals size of rooms.
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
if(rooms == null || rooms.size() == 0) return false;
Set<Integer> visited = new HashSet<>();
visitBFS(rooms, 0, visited);
return visited.size() == rooms.size();
}
private void visitDFS(List<List<Integer>> rooms, Integer i, Set<Integer> visited) {
if(visited.contains(i)) return;
visited.add(i);
for(Integer key : rooms.get(i)) {
visitDFS(rooms, key, visited);
}
}
private void visitBFS(List<List<Integer>> rooms, Integer i, Set<Integer> visited) {
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(i);
while(!queue.isEmpty()){
Integer key = queue.poll();
visited.add(key);
for(Integer k : rooms.get(key)){
if(!visited.contains(k)){
queue.offer(k);
}
}
}
}
