华为 OD 训练营 · 题解精讲
LC841. 钥匙和房间
LC841. 钥匙和房间 视频地址：https://uha.xet.tech/s/4iPP5q
题目描述
有 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 号房间。
题目解析
解题思路
本题本质是有向图的遍历问题。将每个房间看作图中的一个节点，房间内的钥匙列表表示从该节点出发的有向边。题目要求判断从 0 号节点出发，能否遍历所有节点。
参考代码提供了 DFS 和 BFS 两种实现，核心思想一致：从 0 号房间开始，沿着获得的钥匙（即边）访问新房间，并记录已访问的房间。最终检查是否所有房间都被访问过。
关键步骤
1. 初始化：创建长度为 n 的布尔数组 check，初始全为 False，表示所有房间都未进入。 2. 从 0 号房间开始遍历：
- DFS 实现：递归函数
dfs(cur_room)先标记check[cur_room] = True，然后遍历rooms[cur_room]中的每个房间号nxt_room，若未访问则递归调用。 - BFS 实现：使用队列，初始将 0 号房间入队并标记。每次弹出队首
cur_room，遍历其钥匙列表，将未访问的房间入队并标记。
3. 结果判断：遍历结束后，调用 all(check) 检查是否所有房间都被标记为 True。
示意图（DFS 遍历过程）：
rooms = [[1],[2],[3],[]]
check = [F,F,F,F]
dfs(0) → check[0]=T
→ 钥匙1 → dfs(1) → check[1]=T
→ 钥匙2 → dfs(2) → check[2]=T
→ 钥匙3 → dfs(3) → check[3]=T
最终 check = [T,T,T,T] → 返回 True复杂度分析
- 时间复杂度：O(n + m)，其中 n 为房间数，m 为钥匙总数（即所有 rooms[i] 的长度之和）。每个房间最多被访问一次，每条边（钥匙）最多被遍历一次。
- 空间复杂度：O(n)。
check数组占用 O(n)；DFS 递归栈深度最坏为 O(n)，BFS 队列最坏也存储 O(n) 个节点。
参考代码
DFS解法
# 题目：LC841. 钥匙和房间
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问
class Solution:
def dfs(self, cur_room, rooms, check):
# 标记当前房间cur_room为已检查过
check[cur_room] = True
# 遍历从当前房间能进入的所有其他房间nxt_room
for nxt_room in rooms[cur_room]:
# 如果下一个房间nxt_room还没有检查过
if check[nxt_room] == False:
# 对下一个房间nxt_room进行DFS
self.dfs(nxt_room, rooms, check)
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
n = len(rooms)
# 构建检查列表
check = n * [False]
# 从0开始进行深搜
self.dfs(0, rooms, check)
# 检查是否所有房间都进入了
return all(check)
BFS解法
# 题目：LC841. 钥匙和房间
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
# 获得房间数量
n = len(rooms)
# 构建检查列表
check = [False] * n
# 构建队列
q = deque([0])
# 标记起始房间0为已经检查过
check[0] = True
# 进行BFS
while len(q) > 0:
# 弹出队头元素，获得BFS进行到的当前房间cur_room
cur_room = q.popleft()
# 遍历所有从当前房间cur_room能够到达的下一个房间nxt_room
for nxt_room in rooms[cur_room]:
# 下一个房间nxt_room必须没有检查过
if check[nxt_room] == False:
# 将nxt_room修改为已经检查过
check[nxt_room] = True
# 将nxt_room加入队列
q.append(nxt_room)
# 检查是否所有房间都进入了，返回答案
return all(check)