841. 钥匙和房间 (opens new window)

1.深搜

搜索时只要保证两点：

• 每个房间只访问一次，访问过的房间visit使用位上进行标记。
• 房间的每一把钥匙都需要判断是否访问过。

class Solution {
    boolean[] visit;
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        visit=new boolean[rooms.size()];
        //扫荡不上锁的房间
        for(int i=0;i<rooms.size();i++){
            if(rooms.get(i).size()==0)visit[i]=true;
        }
        //从0号开搜
        visit[0]=true;
        dfs(rooms,rooms.get(0));
        for(int i=0;i<visit.length;i++){
            if(!visit[i]) return false;
        }
        return true; 
    }
    //只要保证两点：1.每个房间只访问一次 2.访问的房间 每一把钥匙 都需要查看验货
    public void dfs(List<List<Integer>> rooms,List<Integer> path){
        for(int i=0;i<path.size();i++){
            int roomNo=path.get(i);
            if(!visit[roomNo]){
                visit[roomNo]=true;
                dfs(rooms,rooms.get(roomNo));
            }
        }
    }
}