题型地图 56天全屏 141题

当前：LC841 · LC841 钥匙和房间：从 0 号房间出发，能否进入所有房间 · 首次出现于 Day 32 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

134 / 141回到 Day 32 卡片 141 题索引

LC841

LC841 钥匙和房间：从 0 号房间出发，能否进入所有房间

你有 n 个房间，一开始只有 0 号房间是打开的。每个房间里可能有一些钥匙，房间 i 里的钥匙 x 表示可以打开 x 号房间。问题是：从 0 号房间出发，最后能不能进入所有房间？

时间复杂度：O(n + m)空间复杂度：O(n)有向图可达性

module 1

题目在问什么

你有 n 个房间，编号从 0 到 n-1。

一开始只有 0 号房间是打开的。

每个房间里可能有一些钥匙。

如果房间 i 里有钥匙 x，表示可以打开 x 号房间。

问题是：从 0 号房间出发，最后能不能进入所有房间？

两种结局

所有房间都能进 → 返回 true

有房间永远进不去 → 返回 false

module 2

rooms 输入怎么读

rooms = [[1,3],[3,0,1],[2],[0]]

Room 0里有钥匙 1、3

Room 1里有钥匙 3、0、1

Room 2里有钥匙 2

Room 3里有钥匙 0

每个 rooms[i] 是一个列表，里面的每个数字都是一把钥匙。钥匙 x 表示「我可以打开 x 号房间」。

module 3

为什么这是图

房间 = 图里的节点
钥匙 = 有向边
rooms[i] 里的 key 表示从 i 号房间可以走到 key 号房间
所以问题变成：从节点 0 出发，能不能到达所有节点？

钥匙 → 有向边

Room 0──key 1──▶Room 1

Room 0──key 3──▶Room 3

Room 1──key 3──▶Room 3

Room 1──key 0──▶Room 0

Room 3──key 0──▶Room 0

建好图后，问题就变成：从节点 0 出发，沿着这些箭头能不能走到所有节点。

warm up

先补概念

房间 Room

图里的一个节点，编号 0 到 n-1。

一开始只有 0 号房间是打开的，其它房间都锁着。

钥匙 Key

一条有向边：room i 里的 key x 指向 room x。

拿到钥匙 x，就能打开 x 号房间，相当于走一条 i → x 的边。

有向图可达性

从 0 出发，沿着边能不能走到所有节点。

这题不求最短路、也不复制图结构，只问「能不能全部到达」。

DFS / BFS

用栈（DFS）或队列（BFS）把能到的房间一个个走完。

栈是后进先出，队列是先进先出，遍历到的房间集合是一样的。

visited

记录哪些房间已经访问过。

防止重复进入同一个房间，也防止房间互相有钥匙时陷入死循环。

stack / queue

待处理房间的容器。

拿到新钥匙、且对应房间没访问过时，把它放进来等着处理。

module 4

交互动画实验台

切换示例

帧 1/12

当前步骤

Step 0：读懂 rooms 输入

输入 rooms = [[1,3],[3,0,1],[2],[0]]。Room 0 里有钥匙 1、3，钥匙 x 表示可以打开 x 号房间。问从 0 号房间出发能不能进入所有房间。

rooms = [[1,3],[3,0,1],[2],[0]]

左侧：房间视角

Room 0锁住

Room 1锁住

301

Room 2锁住

Room 3锁住

中间：图视角

黄色：当前正在处理

绿色：已访问

灰色：还没访问

红色：永远到不了

右侧：机器状态

stack（DFS 栈）右端是栈顶 pop

（本帧栈暂时为空）

visited 数组

[0]

false

[1]

false

[2]

false

[3]

false

当前 room

—

读取到的 keys

—

本轮动作：先读题：钥匙就是有向边，问题是「从 0 能不能到所有房间」。

观察顺序：先看「右侧 stack 取出谁」→「左侧哪个房间被打开」→「中间图上谁高亮」→「visited 哪一格变 true」。

module 5

为什么不会死循环

房间之间可能互相有钥匙，例如 0 能到 1，1 又能回到 0。

如果没有 visited，算法会反复进入同一个房间。

所以每次拿到钥匙时，先判断这个房间是否访问过：

没访问过：加入 stack/queue。

访问过：跳过。

3 → key 0：visited[0] 已是 true → 跳过

否则 0 → 1 → 0 → 1 …… 永远循环

module 6

代码讲解（Go）

1func canVisitAllRooms(rooms [][]int) bool {2    n := len(rooms)3    visited := make([]bool, n)4 5    stack := []int{0}6    visited[0] = true7 8    for len(stack) > 0 {9        room := stack[len(stack)-1]10        stack = stack[:len(stack)-1]11 12        for _, key := range rooms[room] {13            if !visited[key] {14                visited[key] = true15                stack = append(stack, key)16            }17        }18    }19 20    for _, ok := range visited {21        if !ok {22            return false23        }24    }25 26    return true27}

lines 2-3

记录访问状态

visited 是一个长度为 n 的布尔数组，记录哪些房间已经打开。它是 O(n) 空间，也是这题不能写 O(1) 空间的原因。

lines 5-6

从 0 号房间出发

0 号房间一开始就是打开的，所以先把 0 入栈，并标记 visited[0] = true。这是遍历的起点。

lines 8-10

主循环：取出一个房间

只要栈不空，就从栈顶取一个房间来处理。DFS 用栈（后进先出），换成队列就是 BFS。

lines 12-16

遍历钥匙：没访问过才入栈

读取当前房间里的每一把钥匙 key。如果 visited[key] 还是 false，就标记成 true 并入栈；如果已经访问过，就跳过——这一步就是防止死循环的关键。

lines 20-26

结束判断

遍历结束后扫描 visited，只要有一个房间是 false，就返回 false；全部为 true 才返回 true。

module 7

面试表达

这道题可以建模成有向图可达性问题。每个房间是一个节点，房间里的钥匙表示从当前节点指向其他节点的有向边。从 0 号房间开始做 DFS 或 BFS，用 visited 记录已经访问过的房间，避免重复访问和环。遍历结束后，如果 visited 中所有房间都是 true，说明所有房间都能访问，否则返回 false。时间复杂度 O(n + m)，空间复杂度 O(n)。

复杂度 · n=房间数，m=钥匙总数

时间O(n + m)

n 是房间数量，m 是所有钥匙的总数（每个 rooms[i] 长度加起来）。每个房间最多入栈一次，每把钥匙最多被检查一次，所以是 O(n + m)。

空间O(n)

visited 数组占 O(n)，stack 最坏情况下要装下所有房间，也是 O(n)。这里不是 O(1) 空间，因为必须记录访问状态。