本文共 1591 字，大约阅读时间需要 5 分钟。

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: trueExplanation:  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: falseExplanation: 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 .

题意：N 个房间，开始位于 0 号房间，每个房间有一些钥匙可以进入其他房间。判断是否能够进入每个房间。

思路：DFS一遍过。这个中等题太简单了。代码如下：

class Solution {
   public:    vector
   
     visited;    void dfs(const vector
    
     
      > &rooms, int idx) {
           visited[idx] = true;        for (const int key : rooms[idx])            if (!visited[key])                dfs(rooms, key);    }    bool canVisitAllRooms(vector
      
       
        >& rooms) {
           if (rooms.size() <= 1) return true;        visited.resize(rooms.size());        dfs(rooms, 0);        for (const bool f : visited)            if (!f) return false;        return true;    }};
       
      
     
    
   

转载地址：https://memcpy0.blog.csdn.net/article/details/108332970 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！