Skip to main content

841.钥匙和房间

力扣题目链接leetcode.cn力扣题目链接/problems/keys-and-rooms/

有 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：

  • 输入: [[1],[2],[3],[]]
  • 输出: true
  • 解释: 我们从 0 号房间开始，拿到钥匙 1。 之后我们去 1 号房间，拿到钥匙 2。 然后我们去 2 号房间，拿到钥匙 3。 最后我们去了 3 号房间。 由于我们能够进入每个房间，我们返回 true。

示例 2：

  • 输入：[[1,3],[3,0,1],[2],[0]]
  • 输出：false
  • 解释：我们不能进入 2 号房间。

思路​

本题其实给我们是一个有向图， 意识到这是有向图很重要！

图中给我的两个示例：[[1],[2],[3],[]]``[[1,3],[3,0,1],[2],[0]]，画成对应的图如下：

我们可以看出图1的所有节点都是链接的，而图二中，节点2 是孤立的。

这就很容易让我们想起岛屿问题，只要发现独立的岛，就是不能进入所有房间。

此时也容易想到用并查集的方式去解决。

但本题是有向图，在有向图中，即使所有节点都是链接的，但依然不可能从0出发遍历所有边。 给大家举一个例子：

图3：[[5], [], [1, 3], [5]] ，如图：

在图3中，大家可以发现，节点0只能到节点5，然后就哪也去不了了。

所以本题是一个有向图搜索全路径的问题。 只能用深搜（DFS）或者广搜（BFS）来搜。

关于DFS的理论，如果大家有困惑，可以先看我这篇题解：DFS理论基础programmercarl.comDFS理论基础/图论深搜理论基础.html

以下dfs分析 大家一定要仔细看，本题有两种dfs的解法，很多题解没有讲清楚。 看完之后 相信你对dfs会有更深的理解。

深搜三部曲：

  1. 确认递归函数，参数

需要传入二维数组rooms来遍历地图，需要知道当前我们拿到的key，以至于去下一个房间。

同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

所以 递归函数参数如下：

Text
// key 当前得到的可以
// visited 记录访问过的房间
void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
  1. 确认终止条件

遍历的时候，什么时候终止呢？

这里有一个很重要的逻辑，就是在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。

这决定 终止条件怎么写。

首先明确，本题中什么叫做处理，就是 visited数组来记录访问过的节点，该节点默认 数组里元素都是false，把元素标记为true就是处理 本节点了。

如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。

代码就是这样：

Text
// 写法一：处理当前访问的节点
void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
    if (visited[key]) { // 本层递归是true，说明访问过，立刻返回
        return;
    }
    visited[key] = true; // 给当前遍历的节点赋值true
    vector<int> keys = rooms[key];
    for (int key : keys) {
        // 深度优先搜索遍历
        dfs(rooms, key, visited);
    }
}

如果我们是处理下一层访问的节点，而不是当前层。那么就要在 深搜三部曲中第三步：处理目前搜索节点出发的路径的时候对 节点进行处理。

这样的话，就不需要终止条件，而是在 搜索下一个节点的时候，直接判断 下一个节点是否是我们要搜的节点。

代码就是这样的：

Text
// 写法二：处理下一个要访问的节点
void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
    // 这里 没有终止条件，而是在 处理下一层节点的时候来判断
    vector<int> keys = rooms[key];
    for (int key : keys) {
        if (visited[key] == false) { // 处理下一层节点，判断是否要进行递归
            visited[key] = true;
            dfs(rooms, key, visited);
        }
    }
}

可以看出，如果看待 我们要访问的节点，直接决定了两种不一样的写法，很多录友对这一块很模糊，可能做过这道题，但没有思考到这个维度上。

  1. 处理目前搜索节点出发的路径

其实在上面，深搜三部曲 第二部，就已经讲了，因为终止条件的两种写法， 直接决定了两种不一样的递归写法。

这里还有细节：

看上面两个版本的写法中， 好像没有发现回溯的逻辑。

我们都知道，有递归就有回溯，回溯就在递归函数的下面， 那么之前我们做的dfs题目，都需要回溯操作，例如：797.所有可能的路径programmercarl.com797.所有可能的路径/0797.所有可能的路径.html，为什么本题就没有回溯呢？

代码中可以看到dfs函数下面并没有回溯的操作。

此时就要在思考本题的要求了，本题是需要判断 0节点是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

那什么时候需要回溯操作呢？

当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”， 如果不理解的话，去看我写的797.所有可能的路径programmercarl.com797.所有可能的路径/0797.所有可能的路径.html的题解。

以上分析完毕，DFS整体实现C++代码如下：

C++
// 写法一：处理当前访问的节点
class Solution {
private:
    void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
        if (visited[key]) {
            return;
        }
        visited[key] = true;
        vector<int> keys = rooms[key];
        for (int key : keys) {
            // 深度优先搜索遍历
            dfs(rooms, key, visited);
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false);
        dfs(rooms, 0, visited);
        //检查是否都访问到了
        for (int i : visited) {
            if (i == false) return false;
        }
        return true;
    }
};
Text
写法二：处理下一个要访问的节点
class Solution {
private:
    void dfs(const vector<vector<int>>& rooms, int key, vector<bool>& visited) {
        vector<int> keys = rooms[key];
        for (int key : keys) {
            if (visited[key] == false) {
                visited[key] = true;
                dfs(rooms, key, visited);
            }
        }
    }
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool> visited(rooms.size(), false);
        visited[0] = true; // 0 节点是出发节点，一定被访问过
        dfs(rooms, 0, visited);
        //检查是否都访问到了
        for (int i : visited) {
            if (i == false) return false;
        }
        return true;
    }
};

本题我也给出 BFS C++代码，BFS理论基础programmercarl.comBFS理论基础/图论深搜理论基础.html，代码如下：

C++
class Solution {
bool bfs(const vector<vector<int>>& rooms) {
    vector<int> visited(rooms.size(), 0); // 标记房间是否被访问过
    visited[0] = 1; //  0 号房间开始
    queue<int> que;
    que.push(0); //  0 号房间开始

    // 广度优先搜索的过程
    while (!que.empty()) {
        int key = que.front(); que.pop();
         vector<int> keys = rooms[key];
         for (int key : keys) {
             if (!visited[key]) {
                 que.push(key);
                 visited[key] = 1;
             }
         }
    }
    // 检查房间是不是都遍历过了
    for (int i : visited) {
        if (i == 0) return false;
    }
    return true;

}
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        return bfs(rooms);
    }
};

其他语言版本​

Java
class Solution {
     private void dfs(int key, List<List<Integer>>  rooms, List<Boolean> visited) {
        if (visited.get(key)) {
            return;
        }
        visited.set(key, true);
        for (int k : rooms.get(key)) {
            // 深度优先搜索遍历
            dfs(k, rooms, visited);
        }
    }
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        List<Boolean> visited = new ArrayList<Boolean>(){{
            for(int i = 0 ; i < rooms.size(); i++){
                add(false);
            }
        }};
        dfs(0, rooms, visited);
        //检查是否都访问到了
        for (boolean flag : visited) {
            if (!flag) {
                return false;
            }
        }
        return true;
    }
}
Java
// 广度优先搜索
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] visited = new boolean[rooms.size()];    // 用一个 visited 数据记录房间是否被访问
        visited[0] = true;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);           // 第 0 个房间标记为已访问
        while (!queue.isEmpty()) {
            int curKey = queue.poll();
            for (int key: rooms.get(curKey)) {
                if (visited[key]) continue;
                visited[key] = true;
                queue.add(key);
            }
        }
        for (boolean key: visited)
            if (!key) return false;
        return true;
    }
}
Java
// 广度优先遍历(时间优化)
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int count = 1;      // 用来记录可以被访问的房间数目，因为初始状态下 0 号房间可以被访问，所以置为 1
        boolean[] visited = new boolean[rooms.size()];      // 用一个 visited 数据记录房间是否被访问
        visited[0] = true;          // 第 0 个房间标记为已访问
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        while (!queue.isEmpty()) {
            int curKey = queue.poll();
            for (int key: rooms.get(curKey)) {
                if (visited[key]) continue;
                ++count;                // 每访问一个访问房间就让 count 加 1
                visited[key] = true;
                queue.add(key);
            }
        }
        return count == rooms.size();       // 如果 count 等于房间数目，表示能进入所有房间，反之不能
    }
}