leetcode 841 KeysAndRooms 题解

发表于

题目

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:

1
2
3
4
5
6
7
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:

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

Note:

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

解法

总的来说，就是数组的每个位是一个房间，房间中存有通往其他房间的钥匙，从0号房间开始，问是否能走完全部房间。于是马上想到了BFS算法，只要最后所有位置都visit过，就能够走完所有房间。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool canVisitAllRooms(vector<vector<int>>& rooms) {
    vector<int> visited(rooms.size(), 0);	//已到过的房间
    queue<int> tovisit;		//将要去的房间
    tovisit.push(0);
    visited[0] = 1;
    while(!tovisit.empty()){
        int curr = tovisit.front();
        tovisit.pop();
        for(auto r : rooms[curr]){
            if(!visited[r]){
                tovisit.push(r);
                visited[r] = 1;
            }
        }
    }
    for(int i = 0; i < rooms.size(); i++){
        if(!visited[i]){
            return false;
        }
    }
    return true;
}