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

怎样从“你有 n 个房间，一开始只有 0 号房间是打开的。每个房间里可能有一些钥匙，房间 i 里的钥匙 x 表示可以打开 x 号房间。问题是：从 0 号房间出发，最后能不能进入所有房间？”推导出 图 DFS/BFS · 有向图可达性，并证明每次状态变化都不会漏掉答案？

中心结论：把房间看成节点、钥匙看成有向边，从 0 出发做 DFS/BFS，用 visited 标记访问过的房间，避免重复访问和环。

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。最初，除 0 号房间外的其余所有房间都被锁住。你可以自由地在房间之间来回走动。如果能进入每个房间返回 true，否则返回 false。

1 <= rooms.length <= 1000 0 <= rooms[i].length <= 1000 所有房间中的钥匙数量总计不超过 3000。

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

算法最终需要得到或观察：遍历结束后 visited 全 true 返回 true，否则 false。

重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“图搜索前线”，明确答案需要观察什么。
2. 2状态只维护 stack/queue 存待处理房间，visited 数组记录哪些房间已打开。
3. 3转移每一步按照 把房间看成节点、钥匙看成有向边，从 0 出发做 DFS/BFS，用 visited 标记访问过的房间，避免重复访问和环。
4. 4收尾读取 遍历结束后 visited 全 true 返回 true，否则 false。，并复核边界与复杂度。

先把题目对象翻译成节点和边，再选择 BFS 或 DFS。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：stack/queue 存待处理房间，visited 数组记录哪些房间已打开。

给出一个房间数组，每个房间里面装了一些钥匙。0 号房间默认是可以进入的，房间进入顺序没有要求，问最终能否进入所有房间。 用 DFS 依次深搜所有房间的钥匙，如果都能访问到，最终输出 true。这题算是 DFS 里面的简单题。

把房间看成节点、钥匙看成有向边，从 0 出发做 DFS/BFS，用 visited 标记访问过的房间，避免重复访问和环。

执行过程中持续维护：stack/queue 存待处理房间，visited 数组记录哪些房间已打开。

正确性依赖以下不变量：从 0 号节点出发的有向图可达性问题，不要求回到 0。；visited 防止重复访问同一个房间，也避免房间互相有钥匙时死循环。

面试时可以压缩为：建模成有向图可达性：房间是节点、钥匙是有向边，从 0 做 DFS/BFS，用 visited 避免重复访问和环，最后看 visited 是否全 true。时间 O(n+m)，空间 O(n)。

落到当前题，执行机制可以压缩为：把房间看成节点、钥匙看成有向边，从 0 出发做 DFS/BFS，用 visited 标记访问过的房间，避免重复访问和环。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入你有 n 个房间，一开始只有 0 号房间是打开的。每个房间里可能有一些钥匙，房间 i 里的钥匙 x 表示可以打开 x 号房间。问题是：从 0 号房间出发，最后能不能进入所有房间？ 因为：把房间看成节点、钥匙看成有向边，从 0 出发做 DFS/BFS，用 visited 标记访问过的房间，避免重复访问和环。
2. 2从 0 号房间出发做 DFS0 号房间一开始就是打开的，入栈。 因为：钥匙是有向边，从 0 出发遍历所有可达房间。
3. 3访问 Room 0，钥匙 [1,3]Room 0 的钥匙打开了 Room 1、3，入栈等待处理。 因为：visited 防止重复访问同一个房间，也避免房间互相有钥匙时死循环。
4. 4访问 Room 3，钥匙 [0]Room 3 的钥匙对应房间都访问过，visited 把它们挡住，跳过。 因为：visited 防止重复访问同一个房间，也避免房间互相有钥匙时死循环。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6访问 Room 1，钥匙 [3,0,1]Room 1 的钥匙对应房间都访问过，visited 把它们挡住，跳过。 因为：visited 防止重复访问同一个房间，也避免房间互相有钥匙时死循环。
7. 7Room 2 永远到不了遍历结束后扫描 visited，判断能否进入所有房间。 因为：有向图可达性：从 0 能走到每个节点则返回 true。
8. 8收尾与复杂度遍历结束后 visited 全 true 返回 true，否则 false。 因为：时间 O(n + m) · 空间 O(n)。把房间看成节点、钥匙看成有向边，从 0 出发做 DFS/BFS，用 visited 标记访问过的房间，避免重复访问和环。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func canVisitAllRooms(rooms [][]int) bool {
	visited := make(map[int]bool)
	visited[0] = true
	dfsVisitAllRooms(rooms, visited, 0)
	return len(rooms) == len(visited)
}

func dfsVisitAllRooms(es [][]int, visited map[int]bool, from int) {
	for _, to := range es[from] {
		if visited[to] {
			continue
		}
		visited[to] = true
		dfsVisitAllRooms(es, visited, to)
	}
}

func main() {
    // 1. 主例
    //    输入：mode="keys-and-rooms", rooms=[[1,3],[3,0,1],[2],[0]]
    //    期望：遍历结束后 visited 全 true 返回 true，否则 false。
    //
    // 2. 失败 / 未命中
    //    检查：钥匙在房间内，rooms[i] 的每个值都是一条 i → key 的有向边。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC207 课程表 · 有向图拓扑；LC547 省份数量 · 无向图连通块；LC1971 寻找图中是否存在路径
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意你有 n 个房间，一开始只有 0 号房间是打开的。每个房间里可能有一些钥匙，房间 i 里的钥匙 x 表示可以打开 x 号房间。问题是：从 0 号房间出发，最后能不能进入所有房间？
2. 2重复重复从多个位置搜索会反复访问同一状态；统一的 visited 与前线结构让每个状态只处理一次。
3. 3优化把房间看成节点、钥匙看成有向边，从 0 出发做 DFS/BFS，用 visited 标记访问过的房间，避免重复访问和环。
4. 4证明从 0 号节点出发的有向图可达性问题，不要求回到 0。；visited 防止重复访问同一个房间，也避免房间互相有钥匙时死循环。
5. 5复杂度时间 O(n + m)，空间 O(n)