LC841. 钥匙和房间

题目描述

有 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 号房间。

题目解析

题目在说什么

想象你是一个探险家，面前有 n 个房间，编号从 0 到 n-1。一开始，只有 0 号房间的门是开着的，其他房间都锁着。每个房间里可能放着一些钥匙，每把钥匙上标着一个房间号，表示这把钥匙能打开哪个房间。你进入一个房间后，可以拿走里面所有的钥匙，然后用它们去打开其他锁着的房间。

问题是：给你一个数组 rooms，其中 rooms[i] 是一个列表，里面写着你在 i 号房间能拿到的所有钥匙（也就是能打开的房间号）。你需要判断，从 0 号房间出发，能不能最终进入所有房间。

比如第一个例子：rooms = [[1],[2],[3],[]]，意思是：

• 在 0 号房间，你能拿到 1 号房间的钥匙。
• 在 1 号房间，你能拿到 2 号房间的钥匙。
• 在 2 号房间，你能拿到 3 号房间的钥匙。
• 在 3 号房间，什么钥匙都没有。

你从 0 号开始，拿到钥匙 1 → 打开 1 号 → 拿到钥匙 2 → 打开 2 号 → 拿到钥匙 3 → 打开 3 号。所有房间都进去了，所以返回 true。

第二个例子：rooms = [[1,3],[3,0,1],[2],[0]]，你从 0 号出发，能拿到 1 和 3 的钥匙，然后可以进 1 号和 3 号。但 2 号房间的钥匙在 1 号房间里吗？1 号房间的钥匙列表是 [3,0,1]，没有 2。3 号房间的钥匙是 [0]，也没有 2。所以你永远拿不到 2 号房间的钥匙，进不去，返回 false。

思路是怎么来的

这个问题本质上是一个“能不能走遍所有地方”的问题。你可以把每个房间想象成一个“地点”，房间里的钥匙就是“通往其他地点的路径”。从 0 号地点出发，沿着路径走，看能不能到达所有地点。

这很像一个经典的“图遍历”问题。图就是由节点（房间）和边（钥匙）组成的。你从起点（0 号房间）出发，沿着边（钥匙）走到其他节点，然后继续走，直到走不动为止。最后检查一下，是不是所有节点都到过了。

那怎么实现“沿着钥匙走”呢？有两种常见方法：深度优先搜索（DFS）和广度优先搜索（BFS）。

• DFS 就像你走进一个房间后，先不急着看其他钥匙，而是先拿一把钥匙，立刻去那个房间，然后在新房间里再拿一把钥匙继续深入，直到走到底（没有新钥匙了），再回头去试其他钥匙。就像探险时先走一条路走到黑，再回来走另一条。
• BFS 就像你走进一个房间后，先把这个房间里所有钥匙对应的房间都记下来，然后一个一个去，每到一个新房间，又把新房间的钥匙记下来，再继续。就像先探索完离起点最近的所有房间，再探索更远的。

两种方法都能解决问题，核心就是：从 0 号开始，不断用拿到的钥匙去打开新房间，同时记录哪些房间已经去过了，避免重复走。最后看记录里是不是所有房间都标记为“去过”。

代码逐步拆解

我们先用 DFS 的代码来拆解，因为它的逻辑更直观。

class Solution {
    // 定义DFS函数
    private void dfs(int curRoom, List<List<Integer>> rooms, boolean[] check) {
        // 标记当前房间curRoom为已检查过
        check[curRoom] = true;
        // 遍历从当前房间能进入的所有其他房间nxtRoom
        for (int nxtRoom : rooms.get(curRoom)) {
            // 如果下一个房间nxtRoom还没有检查过
            if (!check[nxtRoom]) {
                // 对下一个房间nxtRoom进行DFS
                dfs(nxtRoom, rooms, check);
            }
        }
    }

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        // 构建检查列表
        boolean[] check = new boolean[n];
        // 从0开始进行深搜
        dfs(0, rooms, check);
        // 检查是否所有房间都进入了
        for (boolean c : check) {
            if (!c) {
                return false;
            }
        }
        return true;
    }
}

第一步：主函数 `canVisitAllRooms` 里做了什么？

1. int n = rooms.size(); 先知道一共有几个房间，比如 n=4。 2. boolean[] check = new boolean[n]; 创建一个布尔数组，长度等于房间数。每个位置默认是 false，表示这个房间还没去过。比如一开始 check = [false, false, false, false]。 3. dfs(0, rooms, check); 从 0 号房间开始，调用 DFS 函数。这个函数会递归地走遍所有能到的房间，并把对应的 check 位置改成 true。 4. 最后用一个循环检查 check 数组：如果有一个位置还是 false，说明那个房间没去过，返回 false；否则返回 true。

第二步：DFS 函数 `dfs` 里做了什么？

• check[curRoom] = true; 一进入当前房间，立刻标记为“已去过”。这样以后就不会再重复进来了。
• for (int nxtRoom : rooms.get(curRoom)) 遍历当前房间里的所有钥匙（即 rooms[curRoom] 这个列表里的每个数字）。比如在 0 号房间，rooms[0] = [1]，所以 nxtRoom 就是 1。