841. Keys and Rooms

Question

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Solution

BFS，创建一个数组记录房间是否被访问。（用DFS搜素亦可。）

如果钥匙对应的房间已经访问过则跳过。
如果未访问过则记录为已访问并加入队列。

最后遍历一次访问状态，如果有没访问过的房间则返回false。反之返回true。

Code

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[] visited = new int[rooms.size()];
        visited[0] = 1;
        Queue<List<Integer>> q = new LinkedList<>();
        q.add(rooms.get(0));
        
        while(!q.isEmpty()){
            List<Integer> keys = q.poll();
            for(int key : keys){
                if(visited[key] == 1) continue;
                visited[key] = 1;
                q.add(rooms.get(key));
            }
        }
        
        for(int i=1; i<rooms.size(); i++){
            if(visited[i] == 0) return false;
        }
        return true;
    }
}