【LeetCode75】第四十三题钥匙和房间-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode75】第四十三题钥匙和房间。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

示例：

分析：

代码：

题目：

【LeetCode75】第四十三题钥匙和房间,LeetCode75题解,深度优先,算法,leetcode,数据结构,c++

示例：

【LeetCode75】第四十三题钥匙和房间,LeetCode75题解,深度优先,算法,leetcode,数据结构,c++

分析：

给我们一个数组，表示对应的房间里拥有能开启的对应索引号的钥匙。

一开始我们只能进入0号房间，也就是数组里索引号为0的位置。数组索引为0的位置里的元素就是我们能拿到的钥匙，可以开启对应房间号的门。我们可以再次进入到这些能够进入的房间，再拿到房间里的钥匙……

问我们最后能不能进入到所有的房间。

那么这道题是一眼就能看出来要使用BFS或是DFS来解题的了。

那我个人比较喜欢DFS，那我就用DFS来做。

首先我们先定义一个长度为房间数量的数组，元素类型为bool类型，用来表示我们能否进入到对应的房间。

一开始我们是只能进入到0号房间，也只能拿到0号房间里的钥匙

接着我们开始递归，在递归里遍历0号房间的钥匙，如果钥匙对应的房间我们是之前就可以进入的，那么我们跳过这把钥匙，因为该房间我们现在或者是之前已经递归过了，为了剪枝，我们就跳过这把钥匙。

如果钥匙对应的房间我们之前没有进入过，那么我们将一开始定义的那个数组中对应的位置置为true表示我们可以进入。再拿到这个房间里的钥匙，开始下一轮递归……

最终DFS结束，我们检查是否所有房间都是可以进入的即可。

【LeetCode75】第四十三题钥匙和房间,LeetCode75题解,深度优先,算法,leetcode,数据结构,c++ 文章来源地址https://www.toymoban.com/news/detail-689463.html

代码：

class Solution {
public:
    void dfs(vector<bool>&temp,vector<vector<int>>& rooms,vector<int> key){
        for(int k:key){ //遍历我们有的钥匙
            if(temp[k]) continue;   //如果我们能进入对应的房间,那么我们之前遍历过了,这边剪枝.
            temp[k]=true;   //如果之前不能进入,那么现在可以进了,那么做个标记
            dfs(temp,rooms,rooms[k]);   //再接着递归现在进入的房间里内含的钥匙
        }
    }
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<bool>temp(rooms.size(),false);   //是否能进入对应房间
        temp[0]=true;   //首先我们是可以进入到第一个房间
        dfs(temp,rooms,rooms[0]);   //dfs,传入可以进的房间,以及每个房间内含钥匙情况,和我们已经有的钥匙
        for(bool t:temp){   //遍历能否进入房间的情况,如果都可以进就返回true.
            if(!t) return false;
        }
        return true;
    }
};

到了这里，关于【LeetCode75】第四十三题钥匙和房间的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！