钥匙和房间
有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j]由[0,1，…，N-1]中的一个整数表示，其中 N=rooms.length。钥匙 rooms[i][j]=v 可以打开编号为 v 的房间。
最初，除 0 号房间外的其余所有房间都被锁住。
你可以自由地在房间之间来回走动。
如果能进入每个房间返回 true，否则返回 false
示例：
输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1
之后我们去 1 号房间，拿到钥匙 2
然后我们去 2 号房间，拿到钥匙 3
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入2号房间。
提示：
- 1<=rooms.length<=1000
- 0<=rooms[i].length<=1000
- 所有房间中的钥匙数量总计不超过 3000
个人理解：
当进入一个房间时，根据钥匙，进入更深的房间，并且标记房间，如果没路了，回来继续进入其他钥匙指向的房间，直到结束。
代码如下(C++):
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int roomCount = rooms.size(); // 获取房间数量
vector<bool> visited(roomCount, false); // 定义可访问房间
visited[0] = 1; // 从第0房间开始
stack <int> keys; // 钥匙栈
keys.push(0);
while(!keys.empty()) // DFS
{
int key = keys.top();
keys.pop();
int rs = rooms[key].size();
for(int i = 0; i < rs; ++i) // 把房间里的钥匙遍历
{
if(!visited[rooms[key][i]]) // 如果这个钥匙去的地方我们可以进入，就不添加钥匙
{
visited[rooms[key][i]] = true; // 否则添加
keys.push(rooms[key][i]); // 然后把钥匙推入栈，继续走
}
}
}
for(int i = 1; i < roomCount; i++){ // 遍历所有添加进去的可访问房间
if(!visited[i]) return false; // 任何一个错误，就返回false
}
return true;
}
};
放在最后
如果您喜欢我的文章，拜托点赞+收藏+关注，博主会根据大家喜好来推出相关系列文章～
更多精彩内容也可以访问我的博客Aelous-BLog
