题目

https://leetcode-cn.com/problems/keys-and-rooms/

简析

这个题比较简单，从0开始，逐个向下搜索就可以了，借助一个数组b[1001]标记能打开的房间，搜索的时候打开了i号房间，b[i]设置为1；搜索结束后，判断数组b中是否还有为0的，如果还有，就返回flase。

第一步 for循环范围

当然是第k个房间里的每一个数啦：

for(int i=0;i<rooms[k].size();i++)

第二步 判断能不能用

• 钥匙都拿到手了，还有什么不能开门的。
• 但是，要判断这个门开过没，钥匙开过了，就不要再开了，不然就死循环了

for(int i=0;i<rooms[k].size();i++){
            if(b[rooms[k][i]]==0){
                
            }
}

第三步 if成立后的处理

• 把钥匙对应的门标记为开过，b[i]=1
• 去开那个门,search那个门，
• 无需回溯

for(int i=0;i<rooms[k].size();i++){
            if(b[rooms[k][i]]==0){
                b[rooms[k][i]]=1;
                search(rooms,rooms[k][i]);
            }
}

完整代码

class Solution {
public:
    int b[1001]={0};
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        b[0]=1;
        search(rooms,0);
        for(int i=0;i<rooms.size();i++)
                if(b[i]==0) return false;
        return true;
    }
    void search(vector<vector<int>>& rooms,int k){
        for(int i=0;i<rooms[k].size();i++){
            if(b[rooms[k][i]]==0){
                b[rooms[k][i]]=1;
                search(rooms,rooms[k][i]);
            }
        }
    }
};