841. Keys and Rooms
給定n個房間,每個房間都會放置0到n把鑰匙,第0個房間總是沒上鎖,求出有沒有辦法
訪問所有房間。
Example:
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.
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.
法一 BFS
思路:
1.利用BFS來求解,首先把第0個房間的鑰匙加入queue,再來每輪從queue中取出
一個鑰匙,若該房間還沒去過則把該房間的所有鑰匙也加入queue並標記該房間
已經走訪過。
2.利用一個變數記錄開鎖的房間數量,最後檢查是否恰好開啟了n房間即可。
Java Code: