LeetCode 841、钥匙和房间

一、题目描述

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

二、题目解析

三、参考代码

1、Java 代码

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;
    }
}

BFS解法

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size(); // 获得房间数量
        boolean[] check = new boolean[n]; // 构建检查列表
        Queue<Integer> q = new ArrayDeque<>(); // 构建队列
        q.offer(0); // 将起始房间0加入队列
        check[0] = true; // 标记起始房间0为已经检查过

        // 进行BFS
        while (!q.isEmpty()) {
            int curRoom = q.poll(); // 弹出队头元素，获得BFS进行到的当前房间curRoom
            // 遍历所有从当前房间curRoom能够到达的下一个房间nxtRoom
            for (int nxtRoom : rooms.get(curRoom)) {
                // 下一个房间nxtRoom必须没有检查过
                if (!check[nxtRoom]) {
                    // 将nxtRoom修改为已经检查过，并将nxtRoom加入队列
                    check[nxtRoom] = true;
                    q.offer(nxtRoom);
                }
            }
        }

        // 检查是否所有房间都进入了，返回答案
        for (boolean c : check) {
            if (!c) {
                return false;
            }
        }
        return true;
    }
}

2、C++ 代码

DFS解法

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

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

BFS解法

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size(); // 获得房间数量
        vector<bool> check(n, false); // 构建检查列表
        queue<int> q; // 构建队列
        q.push(0); // 将起始房间0加入队列
        check[0] = true; // 标记起始房间0为已经检查过

        // 进行BFS
        while (!q.empty()) {
            int curRoom = q.front(); // 弹出队头元素，获得BFS进行到的当前房间curRoom
            q.pop();
            // 遍历所有从当前房间curRoom能够到达的下一个房间nxtRoom
            for (int nxtRoom : rooms[curRoom]) {
                // 下一个房间nxtRoom必须没有检查过
                if (!check[nxtRoom]) {
                    // 将nxtRoom修改为已经检查过，并将nxtRoom加入队列
                    check[nxtRoom] = true;
                    q.push(nxtRoom);
                }
            }
        }

        // 检查是否所有房间都进入了，返回答案
        for (bool c : check) {
            if (!c) {
                return false;
            }
        }
        return true;
    }
};

3、Python 代码

DFS解法

# 题目：LC841. 钥匙和房间
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问

class Solution:
    def dfs(self, cur_room, rooms, check):
        # 标记当前房间cur_room为已检查过
        check[cur_room] = True
        # 遍历从当前房间能进入的所有其他房间nxt_room
        for nxt_room in rooms[cur_room]:
            # 如果下一个房间nxt_room还没有检查过
            if check[nxt_room] == False:
                # 对下一个房间nxt_room进行DFS
                self.dfs(nxt_room, rooms, check)    

    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        # 构建检查列表
        check = n * [False]
        # 从0开始进行深搜
        self.dfs(0, rooms, check)
        # 检查是否所有房间都进入了
        return all(check)

BFS解法

# 题目：LC841. 钥匙和房间
# 难度：中等
# 作者：许老师-闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        # 获得房间数量
        n = len(rooms)
        # 构建检查列表
        check = [False] * n
        # 构建队列
        q = deque([0])
        # 标记起始房间0为已经检查过
        check[0] = True
        # 进行BFS
        while len(q) > 0:
            # 弹出队头元素，获得BFS进行到的当前房间cur_room
            cur_room = q.popleft()
            # 遍历所有从当前房间cur_room能够到达的下一个房间nxt_room
            for nxt_room in rooms[cur_room]:
                # 下一个房间nxt_room必须没有检查过
                if check[nxt_room] == False:
                    # 将nxt_room修改为已经检查过
                    check[nxt_room] = True
                    # 将nxt_room加入队列
                    q.append(nxt_room)

        # 检查是否所有房间都进入了，返回答案
        return all(check)