做个企业网站的公司,极路由 做网站,wordpress主题qux_v7.1,广西网站推广目录
题目#xff1a;
示例#xff1a;
分析#xff1a;
代码#xff1a; 题目#xff1a; 示例#xff1a; 分析#xff1a;
给我们一个数组#xff0c;表示对应的房间里拥有能开启的对应索引号的钥匙。
一开始我们只能进入0号房间#xff0c;也就是数组里索引…目录
题目
示例
分析
代码 题目 示例 分析
给我们一个数组表示对应的房间里拥有能开启的对应索引号的钥匙。
一开始我们只能进入0号房间也就是数组里索引号为0的位置。数组索引为0的位置里的元素就是我们能拿到的钥匙可以开启对应房间号的门。我们可以再次进入到这些能够进入的房间再拿到房间里的钥匙……
问我们最后能不能进入到所有的房间。
那么这道题是一眼就能看出来要使用BFS或是DFS来解题的了。
那我个人比较喜欢DFS那我就用DFS来做。
首先我们先定义一个长度为房间数量的数组元素类型为bool类型用来表示我们能否进入到对应的房间。
一开始我们是只能进入到0号房间也只能拿到0号房间里的钥匙
接着我们开始递归在递归里遍历0号房间的钥匙如果钥匙对应的房间我们是之前就可以进入的那么我们跳过这把钥匙因为该房间我们现在或者是之前已经递归过了为了剪枝我们就跳过这把钥匙。
如果钥匙对应的房间我们之前没有进入过那么我们将一开始定义的那个数组中对应的位置置为true表示我们可以进入。再拿到这个房间里的钥匙开始下一轮递归……
最终DFS结束我们检查是否所有房间都是可以进入的即可。 代码
class Solution {
public:void dfs(vectorbooltemp,vectorvectorint rooms,vectorint key){for(int k:key){ //遍历我们有的钥匙if(temp[k]) continue; //如果我们能进入对应的房间,那么我们之前遍历过了,这边剪枝.temp[k]true; //如果之前不能进入,那么现在可以进了,那么做个标记dfs(temp,rooms,rooms[k]); //再接着递归现在进入的房间里内含的钥匙}}bool canVisitAllRooms(vectorvectorint rooms) {vectorbooltemp(rooms.size(),false); //是否能进入对应房间temp[0]true; //首先我们是可以进入到第一个房间dfs(temp,rooms,rooms[0]); //dfs,传入可以进的房间,以及每个房间内含钥匙情况,和我们已经有的钥匙for(bool t:temp){ //遍历能否进入房间的情况,如果都可以进就返回true.if(!t) return false;}return true;}
};
