AlgoPressAppearance
0841-钥匙和房间
https://leetcode.cn/problems/keys-and-rooms
有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。 当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
示例 1：
输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
示例 2：
输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
提示：
- n == rooms.length
- 2 <= n <= 1000
- 0 <= rooms[i].length <= 1000
- 1 <= sum(rooms[i].length) <= 3000
- 0 <= rooms[i][j] < n
- 所有 rooms[i] 的值 互不相同
思路
统计 入度，最后找出 入度为 0 的数据，表示不能进入那个房间
注意：
- 如果那个房间只放了自己的钥匙，则不能打开自己
- 如果两个钥匙循环放入两个房间了，则也是互相不能打开
- 递归的时候，如果房间已经打开，就不用重新去打开，否则会出现不停循环，堆栈溢出
参考代码
csharp
public class Solution {
int[] ingress;
private void UnlockRooms(IList<IList<int>> rooms, int index){
if(ingress[index] == 0){
//解锁房间
ingress[index] = 1;
//拿到钥匙解锁其他房间
for(int j=0; j<rooms[index].Count; j++){
UnlockRooms(rooms,rooms[index][j]);
}
}
}
public bool CanVisitAllRooms(IList<IList<int>> rooms) {
int n = rooms.Count;
ingress = new int[n];
UnlockRooms(rooms,0);
//寻找结果为0的房间，表示不能打开
for(int i=0; i<n; i++){
if(ingress[i] == 0){
return false;
}
}
return true;
}
}
思路2 【官方，广度优先搜索】
从第一个节点开始，广度优先搜索，通过钥匙访问每个房间，并且记录是否已经访问过 统计最后的访问房间数是否等于总数
通过 BFS 模拟访问顺序，访问过的不再继续访问
csharp
public class Solution {
public bool CanVisitAllRooms(IList<IList<int>> rooms) {
int n = rooms.Count;
int[] visited = new int[n];
Queue<int> myQueue = new Queue<int>();
myQueue.Enqueue(0);
int num = 0;
while(myQueue.Count > 0){
int count = myQueue.Count;
for(int i=0; i<count; i++){
int roomNumber = myQueue.Dequeue();
if(visited[roomNumber] == 0){
visited[roomNumber] = 1;
num++;
foreach(int key in rooms[roomNumber]){
myQueue.Enqueue(key);
}
}
}
}
return num == n;
}
}
复习：20220703
csharp
public class Solution {
private bool[] ingress;
private void dfs(IList<IList<int>> rooms, int room){
if(!ingress[room]){
ingress[room] = true;
//遍历key
foreach(int key in rooms[room]){
dfs(rooms, key);
}
}
}
public bool CanVisitAllRooms(IList<IList<int>> rooms) {
int n = rooms.Count;
ingress = new bool[n];
dfs(rooms,0);
for(int i=0; i<ingress.Length; i++){
if(ingress[i] == false){
return false;
}
}
return true;
}
}