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();
    }
};