有 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
输入: [[1],[2],[3],[]]
输出: true
解释:
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。
示例2
输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。
提示
1 <= rooms.length <= 10000 <= rooms[i].length <= 1000- 所有房间中的钥匙数量总计不超过
3000。
通过总结和简化问题，可提取出以下信息：
- 二维数组
- 每个数组为一个单位（节点）
- 每个单位（节点）可到达其他零个或多个不同单位（节点）
通过分析，我们可以把题目描述的模式转换为一种基本数据结构：图
- 图分为有向图和无向图，联通图和非联通图
- 图的基本存储方式为邻接矩阵（二维数组），邻接表，十字链表，邻接多重表，边集数组
- 图的遍历方式可分为深度遍历和广度便利
- 每个房间有一些钥匙，1号房中有3号钥匙不等同于3号房中有1号钥匙（有向图）
- 最初从
0号房间进入 （从图的一个指定的节点开始） - 是否可以进入每个房间（是否可以遍历完整个图）
在此可以将问题转换为，从图的特定节点出发，可否遍历完整个图。
#解决
图的遍历方式有深度遍历和广度遍历，同时都有递归方式和非递归方式。
深度遍历递归
func canVisitAllRooms2(_ rooms: [[Int]]) -> Bool {
var keyStreams = Dictionary<Int,Bool>();
func visiter(_ index: Int, _ rooms:[[Int]]) {
if let _ = keyStreams[index] {
return;
}
keyStreams[index] = true;
for (_,temp) in rooms[index].enumerated() {
visiter(temp, rooms)
}
}
visiter(0, rooms);
if keyStreams.count == rooms.count {
return true
}
return false
}深度遍历非递归
func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
var keyArrays = Array<Int>()
var keyStreams = Dictionary<Int,Bool>();
keyArrays.append(0)
while keyArrays.count > 0 {
let keyCurrent = keyArrays.popLast();
print(keyCurrent!)
keyStreams[keyCurrent!] = true;
for (_,temp) in rooms[keyCurrent!].enumerated() {
guard let _ = keyStreams[temp] else {
keyArrays.append(temp);
continue;
}
}
}
if keyStreams.count == rooms.count {
return true
}
return false
}广度优先非递归
func canVisitAllRooms3(_ rooms: [[Int]]) -> Bool {
var keyArrays = Array<Int>()
var keyStreams = Dictionary<Int, Bool>();
keyArrays.append(0)
keyStreams[0] = true
while keyArrays.count > 0 {
let keyCurrent = keyArrays.popLast();
let currentKeys = rooms[keyCurrent!]
for temp in currentKeys {
guard let _ = keyStreams[temp] else {
keyStreams[temp] = true
keyArrays.append(temp);
continue;
}
}
}
if keyStreams.count == rooms.count {
return true
}
return false
}