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: