🔑 钥匙和房间
📝 题目描述
有n个房间，房间按从0到n - 1编号。最初，除0号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
给你一个数组rooms，其中rooms[i]是你进入i号房间可以获得的钥匙集合。如果能进入所有房间，返回true，否则返回false。
📋 代码模板
java
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
}
}typescript
function canVisitAllRooms(rooms: number[][]): boolean {
}💡 提示
- 所有
的值互不相同
🚀 示例
🖊️ 题解
DFS
可惜没有如果
java
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
boolean[] visited = new boolean[n];
int enters = dfs(rooms, visited, 0);
return enters == n;
}
private int dfs(List<List<Integer>> rooms, boolean[] visited, int i) {
if (visited[i]) {
return 0;
}
int enters = 1;
visited[i] = true;
for (Integer key : rooms.get(i)) {
enters += dfs(rooms, visited, key);
}
return enters;
}
}typescript
function canVisitAllRooms(rooms: number[][]): boolean {
const n = rooms.length;
const visited: boolean[] = Array(n).fill(false);
const enters = dfs(rooms, visited, 0);
return enters == n;
}
function dfs(rooms: number[][], visited: boolean[], i: number): number {
if (visited[i]) {
return 0;
}
visited[i] = true;
let enters = 1;
for (const key of rooms[i]) {
enters += dfs(rooms, visited, key);
}
return enters;
}BFS
可惜没有如果
java
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
int n = rooms.size();
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
visited[0] = true;
int enters = 1;
while (!queue.isEmpty()) {
int i = queue.poll();
for (Integer key : rooms.get(i)) {
if (visited[key]) {
continue;
}
queue.offer(key);
visited[key] = true;
enters++;
}
}
return enters == n;
}
}typescript
function canVisitAllRooms(rooms: number[][]): boolean {
const n = rooms.length;
const visited: boolean[] = Array(n).fill(false);
const queue: number[] = [];
queue.push(0);
visited[0] = true;
let enters = 1;
while (queue.length > 0) {
const i: number = queue.shift()!;
for (const key of rooms[i]) {
if (visited[key]) {
continue;
}
queue.push(key);
visited[key] = true;
enters++;
}
}
return enters == n;
}