0841. Keys and Rooms¶
题目信息¶
- 题号:
0841
- 难度:
Medium
- 主题:
图、可达性、房间钥匙
- 原题:
- 重点:
初始只能进入房间 0,进入房间后获得其中全部钥匙;判断最终能否访问所有房间
题目重述¶
有 n 个房间,编号为 0 至 n - 1。除房间 0 外,所有房间初始都上锁;你一开始位于房间 0。数组 rooms[i] 列出进入房间 i 后能够拿到的钥匙,每把钥匙的值就是它能打开的房间编号。
拿到钥匙后可以在之后任意时刻进入对应房间,并继续取得其中的钥匙。请判断从房间 0 出发最终能否访问全部房间。
2 <= rooms.length <= 1000,每个房间至多包含 1000 把互不重复的钥匙;所有钥匙总数在 [1, 3000] 范围内,每个钥匙编号都在 [0, n - 1] 范围内。
自建示例¶
不同分支共同通向最后房间:
输入:rooms = [[1,2],[3],[3],[]]
输出:true
解释:从房间 0 获得 1、2 的钥匙,进入任一房间后都能得到房间 3 的钥匙,因此四个房间都可访问。
存在不可达房间:
输入:rooms = [[1],[],[0]]
输出:false
解释:只能访问房间 0 和 1,房间 2 的钥匙始终无法取得。