|
题目意思是给了一个二维数组，比如[[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();
? ? }
};
|