leetcode 841. Keys and Rooms

There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, ..., N-1, and each room may have some keys to access the next room.

Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, ..., N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.

Initially, all the rooms start locked (except for room 0).

You can walk back and forth between rooms freely.

Return true if and only if you can enter every room.

Example 1:

Input: [[1],[2],[3],[]]
Output: true
Explanation:
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3. Since we were able to go to every room, we return true.

Example 2:

Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 2.

Note:

1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
The number of keys in all rooms combined is at most 3000.

这个题的大意是首先在开始的门里面取钥匙，然后依次打开钥匙对应的门，最后看看门是否全部打开。

这个题可以用栈，也可以用队列。在C++和Java有相应的库可以调用。不过，在python中，可以用列表求解。

python代码（基于队列思维）:

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = [False] * len(rooms) # 类似于C++的memset(seen, false, sizeof(seen))。
        seen[0] = True
        q = [0] # 队列
        
        while len(q):
            Q = q.pop(0)    # 弹出队首元素。
            for index in rooms[Q]:
                if not seen[index]:
                    seen[index] = True
                    q.append(index)
        return all(seen)    # 判断seen里面的元素是否都为True，即是否都打开了门。

在栈中，只需要在Q = q.pop(0)那个中改为Q = q.pop()可以了。