requirements

There are N rooms, and you start out in room 0. Each room has a different number: 0,1,2… N-1, and there may be some keys in the room that allow you to enter the next room.

Formally, there is a key list rooms[I] for each room I, and each key room [I][j] is represented by an integer in [0,1,…, n-1], where N = rooms.length. Key rooms[I][j] = v

Initially, all rooms except room 0 were locked.

You can move freely from room to room.

Return true if you can enter each room, false otherwise.

Example 1:

Input: [[1],[2],[3],[] Output: true Explanation: We start with room 0 and get key 1. Then we go to room one and get key two. Then we go to room two and get key three. Finally we went to room 3. Since we were able to enter every room, we return true.Copy the code

Example 2:

Input: [[1, 3], [3, 1], [2], [0]] output: false interpretation: we can't enter the room number 2.Copy the code

The core code

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) - >bool:
        n = len(rooms)
        key = [0 for i in range(0,n)]
        key[0] = 1
        queue = [0]
        while queue:
            newqueue = list(a)for i in queue:
                for k in rooms[i]:
                    if key[k] == 0:
                        key[k] = 1
                        newqueue.append(k)
            queue = newqueue
        return sum(key) == n

Copy the code

This is a BFS, breadth-first traversal problem. We continuously add the rooms we have searched to our queue, until the number of doors we can open is the same as the number of keys we have obtained, so we can complete all the doors.