LeetCode 841. 钥匙和房间
目录
题目描述
题意分析
有
n个编号 0 到n - 1的房间，第i个房间里放着若干把钥匙，每把钥匙上写着一个房间号。一开始只有 0 号房间是开着的，问能否把所有房间都走一遍。问题只要一个布尔答案：不需要最少开门次数，也不需要给出访问顺序，因此过程中的「先开哪间」完全不影响结论。
钥匙可以重复出现、可以指向自己、也可以指向已经开过的房间。这些情况不改变答案，但会让同一个房间被反复处理，是实现上必须压住的地方。
数据规模很小：房间数最多 1000，钥匙总数最多 3000。边界要考虑只有一个房间（直接为真）、0 号房间里一把钥匙都没有（只要还有别的房间就为假）、以及钥匙指向 0 自己这几种情况。
解法：BFS 扩展可达房间
核心思路
最朴素的想法是模拟：从 0 出发，枚举「先用哪把钥匙、再用哪把」的所有顺序，看有没有一种顺序能开完全部房间。这等价于枚举排列，规模是指数级。
瓶颈在于同一个房间会沿不同的开门顺序被反复展开，而「房间 x 是否开过」这件事跟你走哪条路到达它毫无关系。
换成图的视角：把房间看成点，把「
i号房间里有j号钥匙」看成一条有向边i → j，问题就是「从 0 出发能否到达全部点」的可达性判定。可达性只关心最终能到的集合，既不关心顺序也不关心代价，所以任何一次完整遍历都能给出答案，BFS 与 DFS 在这里等价。遍历要维持的不变量是：
visited[x]为真当且仅当x已经被放进过队列。配合「入队的同时立刻标记」，每个房间至多入队一次，于是count恒等于已标记房间的数量，最后拿它和n比较即可。
解题步骤
- 开一个长度为
n的visited数组，把 0 号房间标记为已访问，count置 1。起点必须先标记，否则一旦有钥匙指回 0，它会被当成新房间重复计数。- 队列里放入 0，开始循环出队。队列只是遍历顺序的载体，本题不需要分层，也不必记录步数。
- 每次取出房间
room，遍历rooms[room]里的每把钥匙next。这一步对应「进屋后把里面的钥匙全部收走」。- 只有当
visited[next]为假时，才标记、count++并入队。三个动作必须绑在一起做，任何一个漏掉都会破坏「标记数等于count」这条不变量。- 关键是标记的时机在入队，而不是出队。出队才标记的话，同一个房间可能被多条边同时推进队列，既会重复展开也会让计数虚高。
- 队列耗尽说明从 0 出发的可达集合已经完全展开，此时
count == n就返回真，否则返回假。以
rooms = [[1, 3], [3, 0, 1], [2], [0]]走一遍：初始
visited = [true, false, false, false]，queue = [0]，count = 1。取出 0，它的钥匙是 1 和 3。1 未访问，标记后
count = 2，入队；3 未访问，标记后count = 3，入队。此时queue = [1, 3]，visited = [true, true, false, true]。取出 1，它的钥匙是 3、0、1，三个房间都已标记，全部跳过，队列不变。
取出 3，它的钥匙是 0，已标记，跳过。队列变空。
循环结束，
count = 3而n = 4，返回false。核对一下：2 号房间的钥匙只放在它自己屋里，外面没有任何一把钥匙指向 2，确实永远进不去。
代码实现
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)
}
复杂度分析
- 时间复杂度：$O(n + m)$，其中
n是房间数、m是钥匙总数。有了「入队即标记」，每个房间只出队一次，它屋里的每把钥匙也只被检查一次。- 空间复杂度：$O(n)$，
visited数组固定n个布尔位，队列在最坏情况下同时容纳全部n个房间号，与钥匙数无关。
关键点总结
- 「能否全部访问」这类问法几乎都能翻译成图的可达性，翻译完成后一次遍历就够，不需要枚举顺序。识别出「只问可行性、不问最优」是把指数级降成线性的第一步。
- 无权图上 BFS 与 DFS 对可达性完全等价，选哪个只看实现便利。反过来说，一旦题目开始问最少步数，才轮到 BFS 的层序性质出场。
- 访问标记必须在入队时设置。这不只是性能优化：只要计数和标记不同步，
count就会虚高，判断条件直接失真。- 计数变量的语义要一句话说得清。这里
count是「已标记房间数」而不是「出队次数」，把它钉死之后，每个分支该不该加就一目了然。- 面试视角：写完之后主动补一句「若改成求最少开门次数就用分层 BFS，若钥匙有使用次数限制就要把状态从房间号扩成房间号加剩余次数」，能展示你对模型边界的把握，比多写一种遍历实现更有价值。
易错点总结
- 错误写法：把
visited[next] = true挪到出队之后，而count仍在入队时累加。用rooms = [[1, 1, 1], []]试：房间 1 被连续入队三次，count数成 4，而n只有 2，明明能全部访问却返回false。- 错误写法：忘记把起点 0 预先标记。用
rooms = [[0], []]试：0 号房间的钥匙指向自己，0 被第二次入队使count变成 2，恰好等于n而返回true；可 1 号房间根本没有任何钥匙指向它，正确答案是false。- 错误写法：以为「每个房间都有钥匙指向它就能全访问」，改用入度判断。用
rooms = [[], [2], [1]]试：1 和 2 互持对方钥匙、入度都不为 0，但从 0 出发一步也走不出去，正确答案是false。- 错误写法：拿钥匙总数与房间数做数量推断。用
rooms = [[1], [0], []]试：钥匙 2 把、房间 3 个，任何计数关系都推不出「2 号房间不可达」，可达性只能靠真的走一遍。- 错误写法：递归写 DFS 时把
visited声明成函数内的局部变量，每层各建一份。标记无法跨分支共享，钥匙成环时会无限递归直到栈溢出。- 错误写法：把
visited当成「当前路径上是否出现过」，回溯时撤销标记。可达性不区分路径，撤销标记会让同一房间沿不同路径反复展开，钥匙稠密时复杂度从线性退化成指数。- 错误写法：遍历某个房间的钥匙时误用外层长度，写成
for (int i = 0; i < rooms.size(); i++)再取rooms.get(room).get(i)。用rooms = [[1, 2, 3], [], [], []]试：外层是 4、内层只有 3，第四次取值直接下标越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 133. 克隆图 | 中等 | 遍历骨架相同，但访问时要建立新旧节点的映射 |
| 200. 岛屿数量 | 中等 | 起点不唯一，要枚举全图并统计连通块个数 |
| 207. 课程表 | 中等 | 同为有向图，判的是有无环，需入度或三色标记 |
| 797. 所有可能的路径 | 中等 | 要列出全部路径，只能回溯，不能一次性打标记 |
| 1319. 连通网络的操作次数 | 中等 | 无向图，要数连通块并与可用线缆数做比较 |
| 1466. 重新规划路线 | 中等 | 遍历时需区分边的原始方向并累计翻转次数 |