Sponsored
Sponsored
The idea is to use Depth-First Search (DFS) to explore all reachable rooms starting from room 0. This can be implemented either recursively or iteratively with a stack. We maintain a set of visited rooms and attempt to visit all rooms that we have keys for, recursively adding rooms to the visited set as we access them. The process continues until no new rooms can be explored.
1import java.util.HashSet;
2import java.util.List;
3import java.util.Set;
4
5public class Solution {
6 public boolean canVisitAllRooms(List<List<Integer>> rooms) {
7 Set<Integer> visited = new HashSet<>();
8 dfs(rooms, visited, 0);
9 return visited.size() == rooms.size();
10 }
11
12 private void dfs(List<List<Integer>> rooms, Set<Integer> visited, int room) {
13 if (!visited.contains(room)) {
14 visited.add(room);
15 for (int key : rooms.get(room)) {
16 dfs(rooms, visited, key);
17 }
18 }
19 }
20}This is a Java implementation of the DFS approach. It uses a HashSet to track visited rooms and calls a recursive dfs method to conduct the depth-first traversal starting from room 0. For each unvisited room, we explore rooms for all the keys found in it.
Instead of using DFS, we can also use Breadth-First Search (BFS) to explore the rooms iteratively. We use a queue to maintain the rooms to be visited next. Initially, room 0 is added to the queue. As we visit each room, we add all the keys found in that room to the queue, provided we haven't visited the corresponding rooms yet. This approach ensures a layer-wise exploration similar to BFS.
In this JavaScript solution, a queue is represented by an array. We begin with room 0 enqueued and marked as visited. As long as the queue has elements, the function processes each room, enqueuing any unvisited rooms connected by keys. After the queue is exhausted, the function checks if all rooms were accessed.