原文链接: https://leetcode-cn.com/problems/keys-and-rooms

英文原文

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

 

Example 1:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

Example 2:

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

 

Constraints:

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• All the values of rooms[i] are unique.

中文题目

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙取解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。

 

示例 1：

输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

 

提示：

• n == rooms.length
• 2 <= n <= 1000
• 0 <= rooms[i].length <= 1000
• 1 <= sum(rooms[i].length) <= 3000
• 0 <= rooms[i][j] < n
• 所有 rooms[i] 的值 互不相同

通过代码

高赞题解

解题思路：

这道题仿佛是酒店老板的开房阴谋。想要开所有房间，我给他规划了两个方法。分别叫 BFS 和 DFS。

BFS

BFS，即 广度优先搜索。

老板就问了：“我就是想开房，你能不能讲人话？”
说人话就是，我们按照这个步骤来做——

思路

• 首先找到 0 号房间，把所有 ０ 号房间的钥匙都开一遍。
• 进入刚刚开过的房间，再把它们房间里的钥匙再开一遍。
• 重复以往，层层递进，直到找不到符合要求的节点。

思路很好理解对吧，就是一个从0号房间向外一层层扩散的过程。可是怎么实现呢？

实现

这里就要介绍一下 队列，因为 广度优先搜索 和 队列 是好基友。
什么是队列？就是一个先进先出的数组，和我们日常生活中的排队很像。当我们向队列插入一个新数的时候，它插在最后，当我们取出一个数的时候，要从头取。就像顾客开房，都是要排队的（假设没有 VIP，不许杠！）。

补充——关于在Python中使用队列
在 Python 中，可以使用以下几种方法实现队列

• collections包里的deque，对应操作
  • pop()从尾取出
  • appendleft() 从头插入
• queue包中的queue，对应操作
  • put() 插入
  • get() 取出
• 直接使用list，只要保证只使用
  • pop() 取出
  • insert(0,) 插入
    或者只使用
  • append() 插入
  • list[0]并且del list[0] 取出
    两者使用list方法的不同就区别于你把哪个当头，哪个当尾

三种方法各有优劣。

• 第一种是正统的Python的双端队列，缺点是调用的函数有点复杂，可能一不小心写了append，就不对了。
• 第二种使用封装的函数很直接，put()和get()不容易搞混淆。但是queue类型其实里面本身就装了一个deque，有点脱裤子放X的感觉。
• 第三种优势在于不用调包，但是函数使用逻辑可能造成混淆。在
  这里，完整版代码采用第二种，好理解，精简版代码采用第三种，省行数。三种方式可以按照你的喜好互相替换，完全不影响结果。

这时候老板又问了：“为什么 广度优先搜索 和 队列 能勾搭到一块儿？这和排队有啥关系？”

我们可以这样利用 队列 实现 广度优先搜索。

• 我们设置一个队列，先把初始房间添加进去
• 规定每次从队列取出一个房间
• 把这个房间的所有钥匙放到队列中。
• 当这个队列为空的时候，说明遍历完成

进队列进去的是钥匙，出来的是房间，其实都是一回事，相当于出来的时候就开锁了。

因为队列每次取出的是最后的，而每次添加的是放在最前面，所以可以想象到，每次先处理的都是层级最少的，最接近初始点的，然后慢慢扩大，这样就实现了 广度优先搜索。

老板很好奇：“这个层级顺序有那么重要吗？咱也就是进去看看。”

在这道题目里，层级是 不重要 的，这也是为什么后来还有个深度优先搜索，也可以解决这道题目。但是广度优先搜索的特点就在于这个层级，在很多题目当中它是很重要的。有时候，对队列取出元素的时候，要设置循环，固定住当前的队列项，对当前的队列项操作——因为当前的队列项一定是相同层级的。例如，在我们寻找到达某个节点的最小步数的时候，层级也就是步数就显得尤为重要了。在 leetcode 当中，有很多题都是需要 广度优先搜索 的，这是一种解题的思想，要熟练掌握。而实现这个思想，又离不开 队列。两者相辅相成。

老板 “啪” 地一下打我一拳：“净整这些有的没的，给我写！不然顾客都进来了！”

[]
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited, queue = {0}, [0]
        while queue:
            room_index = queue.pop()
            for key in rooms[room_index]:
                if key not in visited:
                    visited.add(key)
                    queue.insert(0,key)
        return len(visited) == len(rooms)

DFS

DFS，即深度优先搜索。

老板抢着说：“从你这小兔崽子的BFS里，我好想猜到了DFS是什么了，它是不是——”

##$# 思路

• 先找第 ０ 个房间的第一个钥匙
• 进入那个房间，再找它的第一个钥匙
• 重复以往，直到没钥匙了，那么退回刚刚的房间
• 找刚刚房间的第二把钥匙
• 重复以往

思路很好理解对吧，就是一个从中间向一个房间深入的过程。可是怎么实现呢？

实现

还记得标题写的两个方法，三种实现吗？
这是因为 DFS 通常有两种实现方法，一种是 递归，另一种是使用 栈。
这里就要介绍一下 栈，因为 深度优先搜索 和 栈 是好基友。
什么是栈？就是一个后进先出的数组，和我们日常生活中的插队很像。当我们向栈插入一个新数的时候，它插在最前面，当我们取出一个数的时候，要从头取。就像老板插队去开房，他不排队，直接插到第一个位置，下一个服务的就是他。

补充——关于在Python中使用栈
直接使用list即可，只使用它的这两个方法

• pop()
• append()

这时候老板又问了：“为什么 广度优先搜索 和 堆栈` 能勾搭到一块儿？东扯西扯的家伙。”

我们可以这样利用 堆栈实现深度优先搜索。

• 我们设置一个栈，先把第一个房间添加进去
• 规定每次从栈中取出一个钥匙
• 找这个钥匙开的房间，并且把这个房间放到栈中。
• 当这个栈为空的时候，说明遍历完成

因为栈每次取出的是最后的，而每次添加的也在最后，所以可以想象到，每次先处理的都是最深的，然后慢慢扩大，这样就实现了 深度优先搜索。

这时候老板很好奇：“这个深度顺序有那么重要吗？咱就是进去看看。”

在这道题目里，层级是 不重要 的，这也是为什么前面还有个广度优先搜索，也可以解决这道题目。在 leetcode 当中，有很多题都是需要 深度优先搜索的，这是一种解题的思想，要熟练掌握。而实现这个思想，又离不开 栈，递归。两者相辅相成。

老板 “啪” 地一下打我一拳：“净整这些有的没的，给我写！不然顾客都进来了！”

代码一：使用栈

[]
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited, stack = {0}, [0]
        while stack:
            room_index = stack.pop()
            for key in rooms[room_index]:
                if key not in visited: 
                    visited.add(key)
                    stack.append(key)
        return len(visited) == len(rooms)

代码二：使用递归

[]
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited = {0}
        def dfs(room_index,visited):
            visited.add(room_index)
            for key in rooms[room_index]:
                if key not in visited: dfs(key,visited)
        dfs(0,visited)
        return len(visited) == len(rooms)

统计信息

通过次数	提交次数	AC比率
57586	87413	65.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言