leetcode 841. Keys and Rooms

2024-02-27 00:08

文章标签 leetcode keys 841 rooms

本文主要是介绍leetcode 841. Keys and Rooms，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目意思是给了一个二维数组，比如[[1],[2],[3],[]]

数组[0]代表房间0里放的某个房间i的钥匙，比如房间0里放的房间1的钥匙。然后通过房间0里的钥匙去打开房间1，然后继续去拿钥匙。

该问题和密室逃脱一样或者以前的RPG单机游戏仙剑一样，打通某个任务才能解锁另外一个任务。

求能不能访问所有的房间。

读完题目第一个想法就是这个题目和图的遍历很想哦。

房间0相当于图的顶点vertex，房间0里的钥匙相当于顶点的邻居节点。

得到了邻居节点（钥匙）才能访问其他的顶点（房间）。

然后最后的问题就转换成了最后一共访问的节点（房间）是不是全部的节点（房间）。

代码也千篇一律的用bfs，用queue来存储已经访问的和下一步要访问的节点（房间）， unordered_set来存储访问过的节点（房间）。

最后对比下访问过的房间数目和总的房间数目是否一样。

代码如下：

class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
//That is a typicall graphic issue.
//enter the room means access the vertex and the key means the neighber of vertex.
//access the room means enter the queue.
//convert the issue to check whether the size of traveled node is same as the size of defined number os rooms(vertex)
if(rooms.size() == 0 || rooms.size() == 1)
return true;

queue<int> myqueue;
unordered_set<int> accessedRoom;

myqueue.push(0);
accessedRoom.insert(0);

while(!myqueue.empty()) {
int roomID = myqueue.front();
myqueue.pop();

for(auto &key: rooms[roomID]) {
if(accessedRoom.find(key) != accessedRoom.end())
continue;
else{
myqueue.push(key);
accessedRoom.insert(key);
}
}
}
return accessedRoom.size() == rooms.size();
}
};