?841. 鑰匙和房間

?有?n?個房間，房間按從?0?到?n - 1?編號。最初，除?0?號房間外的其余所有房間都被鎖住。你的目標(biāo)是進(jìn)入所有的房間。然而，你不能在沒有獲得鑰匙的時候進(jìn)入鎖住的房間。

當(dāng)你進(jìn)入一個房間，你可能會在里面找到一套不同的鑰匙，每把鑰匙上都有對應(yīng)的房間號，即表示鑰匙可以打開的房間。你可以拿上所有鑰匙去解鎖其他房間。

給你一個數(shù)組?rooms?其中?rooms[i]?是你進(jìn)入?i?號房間可以獲得的鑰匙集合。如果能進(jìn)入?所有?房間返回?true，否則返回?false。

示例 1：

輸入：rooms = [[1],[2],[3],[]]
輸出：true
解釋：
我們從 0 號房間開始，拿到鑰匙 1。
之后我們?nèi)?1 號房間，拿到鑰匙 2。
然后我們?nèi)?2 號房間，拿到鑰匙 3。
最后我們?nèi)チ?3 號房間。
由于我們能夠進(jìn)入每個房間，我們返回 true。

示例 2：

輸入：rooms = [[1,3],[3,0,1],[2],[0]]
輸出：false
解釋：我們不能進(jìn)入 2 號房間。

思路：本題其實給我們是一個有向圖，不必做轉(zhuǎn)換

用bfs方法，從第一個房間開始，拿鑰匙、進(jìn)入另一個房間、拿鑰匙。。。這樣循環(huán)，并最后判斷是否所有房間都進(jìn)入過了

class Solution {
public:bool canVisitAllRooms(vector<vector<int>>& rooms) {if(rooms.empty()) return true;queue<int> q;//visitRooms標(biāo)記對應(yīng)房間是否進(jìn)入過了vector<bool> visitRooms(rooms.size(),false);q.push(0);while(!q.empty()){vector<int> keyRooms=rooms[q.front()];visitRooms[q.front()]=true;q.pop();for(int keyRoom:keyRooms){if(!visitRooms[keyRoom]) q.push(keyRoom);}}for(bool visited:visitRooms){if(!visited) return false;}return true;}
};