[LeetCode] 841. 钥匙和房间

题目描述有 n 个房间房间按从 0 到 n - 1 编号。最初除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房间你可能会在里面找到一套 不同的钥匙每把钥匙上都有对应的房间号即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true否则返回 false。示例输入rooms [[1],[2],[3],[]] 输出true 解释 我们从 0 号房间开始拿到钥匙 1。 之后我们去 1 号房间拿到钥匙 2。 然后我们去 2 号房间拿到钥匙 3。 最后我们去了 3 号房间。 由于我们能够进入每个房间我们返回 true。解题思路BFS/DFS都行参考代码BFS/* 判断能否到所有的房间去, 深搜和广搜都可以实现 *//* 进过的房间, 不再进去了 *//* 没进去的房间, 进去后找到钥匙, 继续访问其他房间 *//* 最后判断是否所有房间都访问过 */classSolution{public:boolcanVisitAllRooms(vectorvectorintrooms){setinthasVisitedRooms;queueintq;q.push(0);while(!q.empty()){intcurRoomIdxq.front();q.pop();hasVisitedRooms.insert(curRoomIdx);// 遍历当前房间的钥匙能访问的房间列表for(inti0;irooms[curRoomIdx].size();i){// 访问过的就不再访问了避免成环if(hasVisitedRooms.find(rooms[curRoomIdx][i])hasVisitedRooms.end()){q.push(rooms[curRoomIdx][i]);}}}returnhasVisitedRooms.size()rooms.size();}};DFS// 对照 BFS 代码只需把队列换成递归即可classSolution{public:boolcanVisitAllRooms(vectorvectorintrooms){dfs(rooms,0);returnhasVisitedRooms.size()rooms.size();}voiddfs(vectorvectorintrooms,intcurRoomIdx){hasVisitedRooms.insert(curRoomIdx);// 遍历当前房间的钥匙能访问的房间列表for(inti0;irooms[curRoomIdx].size();i){// 访问过的就不再访问了避免成环if(hasVisitedRooms.find(rooms[curRoomIdx][i])hasVisitedRooms.end()){dfs(rooms,rooms[curRoomIdx][i]);}}}public:setinthasVisitedRooms;};