LeetCode 841中等图 · DFS
钥匙和房间 图解题解
这道题到底在问什么
从房间 0 出发，进了一个房间就把里面的钥匙都拿上。每把钥匙能开对应编号的房间——只要那个房间还没去过，就走过去继续找钥匙。最后看是不是每间都进过。
- 输入
- rooms = [[1,2],[3],[4,5],[],[6],[],[7],[]]
- 输出
- true（8 间全可达）
最优解：一步一步想明白
- 3记住「先查 visited、没去过才进」这一招，下面每一步都在用它。
- 48 个房间在这里：箭头表示「这个房间里的钥匙能开哪间」。房间 0 已解锁（橙色起点），其余都锁着。
- 5进入房间 0：先记进 visited，再把里面的钥匙拿上——这间有 钥匙 1、2。
- 6房间 0 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 7用房间 0 的钥匙 1：房间 1 还没进过 → 沿这条边走过去，深入它继续找钥匙。
- 8进入房间 1：先记进 visited，再把里面的钥匙拿上——这间有 钥匙 3。
- 9房间 1 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 10用房间 1 的钥匙 3：房间 3 还没进过 → 沿这条边走过去，深入它继续找钥匙。
- 11进入房间 3：先记进 visited，再把里面的钥匙拿上——这间有 没有钥匙。
- 12房间 3 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 13用房间 0 的钥匙 2：房间 2 还没进过 → 沿这条边走过去，深入它继续找钥匙。
- 14进入房间 2：先记进 visited，再把里面的钥匙拿上——这间有 钥匙 4、5。
- 15房间 2 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 16用房间 2 的钥匙 4：房间 4 还没进过 → 沿这条边走过去，深入它继续找钥匙。
- 17进入房间 4：先记进 visited，再把里面的钥匙拿上——这间有 钥匙 6。
- 18房间 4 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 19用房间 4 的钥匙 6：房间 6 还没进过 → 沿这条边走过去，深入它继续找钥匙。
- 20进入房间 6：先记进 visited，再把里面的钥匙拿上——这间有 钥匙 7。
- 21房间 6 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 22用房间 6 的钥匙 7：房间 7 还没进过 → 沿这条边走过去，深入它继续找钥匙。
- 23进入房间 7：先记进 visited，再把里面的钥匙拿上——这间有 没有钥匙。
- 24房间 7 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 25用房间 2 的钥匙 5：房间 5 还没进过 → 沿这条边走过去，深入它继续找钥匙。
- 26进入房间 5：先记进 visited，再把里面的钥匙拿上——这间有 没有钥匙。
- 27房间 5 标记为已访问，加入「已进入」面板。接着逐把钥匙去开它能开的房间。
- 28DFS 走完：8 个房间全部进过（visited 大小 = 房间数）→ 返回 true。从 0 出发，钥匙链能把每间都串起来。
⚠️ 容易写错的地方
✗ 错：不用 visited 去重
✓ 对：进房间前先查 visited，去过就跳过
钥匙可能互相指（A 给 B、B 给 A），不去重会无限递归
✗ 错：只数钥匙不数房间
✓ 对：最后比的是「访问过的房间数 == 总房间数」
能拿到很多钥匙不代表每间都进过
✗ 错：从任意房间开始
✓ 对：必须从房间 0 出发
只有房间 0 一开始是解锁的
完整代码（Python / C++ / Java）
Python
def canVisitAllRooms(rooms):
visited = set()
def dfs(r):
visited.add(r) # 进房间先记下
for key in rooms[r]: # 拿到的每把钥匙
if key not in visited: # 那间还没去过
dfs(key) # 走过去继续
dfs(0) # 从房间 0 出发
return len(visited) == len(rooms)C++
class Solution {
vector<bool> vis;
void dfs(int r, vector<vector<int>>& rooms){
vis[r] = true;
for(int key : rooms[r])
if(!vis[key]) dfs(key, rooms);
}
public:
bool canVisitAllRooms(vector<vector<int>>& rooms){
vis.assign(rooms.size(), false);
dfs(0, rooms);
for(bool b : vis) if(!b) return false;
return true;
}
};Java
class Solution {
private boolean[] vis;
private void dfs(int r, List<List<Integer>> rooms) {
vis[r] = true;
for (int key : rooms.get(r))
if (!vis[key]) dfs(key, rooms);
}
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
vis = new boolean[rooms.size()];
dfs(0, rooms);
for (boolean b : vis) if (!b) return false;
return true;
}
}复杂度
时间
O(n+e)
每个房间进一次、每把钥匙看一次（n 房间、e 钥匙总数）
空间
O(n)
visited 集合 + 递归栈最深 n 层
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 钥匙和房间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
DFS 还是 BFS 都能做吗？+
都行。DFS 用递归 / 栈，BFS 用队列。本质都是从房间 0 出发遍历可达的房间，最后比访问数和房间总数，遍历顺序不影响结果。
怎么判断答案是 false？+
遍历结束后 visited 的大小 < 房间总数，说明有房间的钥匙谁也没有、永远开不了，返回 false。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 钥匙和房间 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。