一題多解 能打開所有房間的門嗎? Keys and Rooms_Leetcode #841 精選75題

Jaye Haych on Unsplash

題目敘述

題目會給我們一個房間陣列rooms，每個房間裡面擁有數量不等，可以打開其他房間的鑰匙。

每一道房間門預設都是鎖住的，只有0號房間的門一開始是打開的。

請問，從0號房間開始拿鑰匙，最終能不能打開所有房間的門?

題目的原文敘述

測試範例

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.

0號們一開始就是打開的。​
從0號房間可以拿到1號房間的鑰匙。
去1號房間可以拿到2號房間的鑰匙。​
去2號房間可以拿到3號房間的鑰匙。

可以打開所有房間的門。​

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.
不管怎麼走，都拿不到2號房間的鑰匙。
無解，返回False，​

約束條件

Constraints:

• n == rooms.length

房間的總數目定義為n

• 2 <= n <= 1000

房間的總數目n 介於 2 ~ 1000 之間。

• 0 <= rooms[i].length <= 1000

每個房間內部可能有0~1000把鑰匙。

代表有些房間進去之後，拿不到別的鑰匙。

• 1 <= sum(rooms[i].length) <= 3000

鑰匙的總數量介於1~3000把之間。

• 0 <= rooms[i][j] < n

每把鑰匙都可以打開對應的門，不會有惡作劇無用的鑰匙。

• All the values of rooms[i] are unique.

單獨每一間房間，內部擁有的鑰匙不會重複。

建立解題模型 與 演算法