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.
1#include <stdbool.h>
2#include <stdlib.h>
3
4void dfs(int** rooms, int* roomsColSize, bool* visited, int room) {
5 if (!visited[room]) {
6 visited[room] = true;
7 for (int i = 0; i < roomsColSize[room]; i++) {
8 dfs(rooms, roomsColSize, visited, rooms[room][i]);
9 }
10 }
11}
12
13bool canVisitAllRooms(int** rooms, int roomsSize, int* roomsColSize) {
14 bool* visited = (bool*)calloc(roomsSize, sizeof(bool));
15 dfs(rooms, roomsColSize, visited, 0);
16 for (int i = 0; i < roomsSize; i++) {
17 if (!visited[i]) {
18 free(visited);
19 return false;
20 }
21 }
22 free(visited);
23 return true;
24}This C implementation applies DFS using a bool array to track visited rooms. Allocating memory dynamically, it visits all rooms that are accessible using keys found in previously visited rooms. After all accessible rooms have been processed, the solution checks if all rooms have been visited and returns the result.
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.
1#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
unordered_set<int> visited;
queue<int> q;
q.push(0);
visited.insert(0);
while (!q.empty()) {
int room = q.front();
q.pop();
for (int key : rooms[room]) {
if (visited.find(key) == visited.end()) {
visited.insert(key);
q.push(key);
}
}
}
return visited.size() == rooms.size();
}
};In the C++ BFS solution, an unordered_set for visited rooms and a queue for unprocessed rooms are used. Begin with room 0 in the queue, and for each room processed, its keys are used to enqueue unvisited rooms. The process completes when the queue is emptied, checking afterward if all rooms were visited.