0841. Keys and Rooms

题目信息

题号:

0841

难度:

Medium

主题:

图、可达性、房间钥匙

原题:

LeetCode 0841

重点:

初始只能进入房间 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 的钥匙始终无法取得。