C++刷leetcode（841. 钥匙和房间）【深度优先搜索】【图】

糖逗

题目描述：

1. 有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
   
2. 
   
3. 在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
   
4. 
   
5. 最初，除 0 号房间外的其余所有房间都被锁住。
   
6. 
   
7. 你可以自由地在房间之间来回走动。
   
8. 
   
9. 如果能进入每个房间返回 true，否则返回 false。
   
10. 
    
11. 示例 1：
    
12. 
    
13. 输入: [[1],[2],[3],[]]
    
14. 输出: true
    
15. 解释:  
    
16. 我们从 0 号房间开始，拿到钥匙 1。
    
17. 之后我们去 1 号房间，拿到钥匙 2。
    
18. 然后我们去 2 号房间，拿到钥匙 3。
    
19. 最后我们去了 3 号房间。
    
20. 由于我们能够进入每个房间，我们返回 true。
    
21. 示例 2：
    
22. 
    
23. 输入：[[1,3],[3,0,1],[2],[0]]
    
24. 输出：false
    
25. 解释：我们不能进入 2 号房间。
    
26. 提示：
    
27. 
    
28. 1 <= rooms.length <=&#160;1000
    
29. 0 <= rooms[i].length <= 1000
    
30. 所有房间中的钥匙数量总计不超过&#160;3000。
    
31. 
    
32. 来源：力扣（LeetCode）
    
33. 链接：https://leetcode-cn.com/problems/keys-and-rooms
    
34. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(vector<vector<int> >& rooms, vector<int>&temp, vector<int>&visit, bool&res, int cur_room){         
   
4.         if(temp.size() == rooms.size()){
   
5.             res = true;
   
6.             return;
   
7.         }
   
8.         int store = 0;
   
9.         for(int i = 0; i < rooms[cur_room].size(); i++){
   
10.             if(visit[rooms[cur_room][i]] == 1) store++;
    
11.         }
    
12.         if(store == rooms[cur_room].size()) return;
    
13.         for(int i = 0 ; i < rooms[cur_room].size(); i++){
    
14.             if(visit[rooms[cur_room][i]] == 0){
    
15.                 temp.push_back(rooms[cur_room][i]);
    
16.                 visit[rooms[cur_room][i]] = 1;
    
17.                 dfs(rooms, temp, visit, res, rooms[cur_room][i]);
    
18.             }
    
19.         }
    
20.     }
    
21.     bool canVisitAllRooms(vector<vector<int>>& rooms) {
    
22.         vector<int>visit(rooms.size(), 0);
    
23.         bool res = false;
    
24.         vector<int> temp;
    
25.         visit[0] = 1;
    
26.         temp.push_back(0);
    
27.         dfs(rooms, temp, visit, res, 0);
    
28.         return res;
    
29.     }
    
30. };

复制代码

糖逗