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.
1var canVisitAllRooms = function(rooms) {
2 const visited = new Set();
3
4 const dfs = (room) => {
5 if (!visited.has(room)) {
6 visited.add(room);
7 for (const key of rooms[room]) {
8 dfs(key);
9 }
10 }
11 };
12
13 dfs(0);
14 return visited.size === rooms.length;
15};The JavaScript solution utilizes a Set to track visited rooms and defines a recursive dfs function. Starting from room 0, the function attempts to visit all rooms using available keys, marking each room as visited.
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.
This Java implementation of BFS uses a LinkedList as a queue. The algorithm starts with room 0 added to the queue. Each room is processed to obtain its keys, and unvisited rooms are added to both visited set and queue. The breadth-first exploration proceeds until no additional rooms can be processed. Finally, it checks if all rooms are visited.