LeetCode 841. 钥匙和房间
题目描述
题意分析
最初只有 0 号房间可以进入。进入一个房间后，可以拿到其中的全部钥匙，再打开钥匙对应的房间。判断从 0 号房间出发，最终能否进入所有房间。
将房间看作节点，房间
a中有房间b的钥匙，就对应一条从a指向b的有向边。题目因此变成判断所有节点是否都能从节点 0 到达。
解法：BFS 扩展可达房间
核心思路
[!blue]
用队列保存已经确定能进入、但还没有检查钥匙的房间，用
visited记录已经发现的房间。开始时把房间 0 标记并入队，访问数量count设为 1。每次取出一个房间，查看其中所有钥匙。钥匙指向的房间若尚未发现，就立刻标记、计数并入队。标记必须在入队时完成，否则多个房间可能同时持有同一把钥匙，导致重复入队和计数。
每个房间只需展开一次：再次进入同一房间，能拿到的仍是同一组钥匙，不会带来新信息。即使钥匙关系构成环，
visited也会让搜索正常结束。队列中的房间都由已可达房间的钥匙打开，因此一定可以进入；任何从 0 出发的可达路径，也会沿着钥匙关系逐步被发现。队列耗尽时，所有能够进入的房间都已统计，比较
count与房间总数即可。
解题步骤
- 建立访问数组和队列，将 0 号房间标记、入队，并初始化
count = 1。- 不断出队一个房间，遍历它的钥匙列表。
- 对尚未标记的目标房间，先标记并增加计数，再加入队列，等待之后处理它的钥匙。
- 队列为空后，若
count等于房间总数就返回true，否则返回false。
代码实现
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] visited = new boolean[rooms.size()];
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
// 起点先标记，指回起点的钥匙不会重复计数
visited[0] = true;
int count = 1;
while (!queue.isEmpty()) {
int room = queue.poll();
for (int next : rooms.get(room)) {
if (!visited[next]) {
// 第一次发现即标记，计数与入队同步
visited[next] = true;
count++;
queue.offer(next);
}
}
}
return count == rooms.size();
}
}
func canVisitAllRooms(rooms [][]int) bool {
visited := make([]bool, len(rooms))
queue := make([]int, 0)
queue = append(queue, 0)
// 起点先标记，指回起点的钥匙不会重复计数
visited[0] = true
count := 1
head := 0
for head < len(queue) {
room := queue[head]
head++
for _, next := range rooms[room] {
if !visited[next] {
// 第一次发现即标记，计数与入队同步
visited[next] = true
count++
queue = append(queue, next)
}
}
}
return count == len(rooms)
}
复杂度分析
设房间数为
n，所有房间的钥匙总数为m。
- 时间复杂度：$O(n+m)$，访问数组初始化为 $O(n)$，每个可达房间及其钥匙至多处理一次。
- 空间复杂度：$O(n)$，来自访问数组和最多容纳
n个房间的队列。
关键点总结
[!green]
- 钥匙关系有方向，从 0 号房间进行一次可达性搜索即可。
- 一个房间的钥匙集合固定，重复进入它不会增加可达信息。
count在首次标记时增加，始终等于已经发现的不同房间数。
易错点总结
[!yellow]
- 只看每个房间是否有入边：钥匙可能藏在从 0 无法到达的房间中，存在钥匙不代表能拿到。
- 把钥匙关系当成无向边：能从一个房间拿到另一个房间的钥匙，并不意味着反向也成立。
- 起点没有提前标记：指回 0 的钥匙会导致重复计数。
- 发现时计数、出队时才标记：同一个房间可能在出队前被多条路径重复发现，应把标记、计数和入队放在一起。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 864. 获取所有钥匙的最短路径 | 困难 | 同样收集钥匙解锁后续位置，原题还需在网格中行走并最小化步数，本题拿到钥匙即可把对应房间加入可达集合。 |
| 1306. 跳跃游戏 III | 中等 | 同样从起点搜索可达状态，原题由数组跳长隐式生成边，本题由钥匙列表显式给出边。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！