🌕 🌗 841. 钥匙和房间

难度: 🌕 🌗

问题描述

---

解法 1 - 递归- 深度优先

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        // 思路：
        // 类似回溯，初始节点可以范围为 [0, len - 1]
        // 从初始节点进入，找到钥匙，且该条路径之前没有走过，则可以继续探索
        // 若已经走过，则该条路探索失败
        // 求的不是能不能一条路径走完所有房间，而是所有路径总和能不能覆盖所有房间
        // 刚开始只能进入 0 号房间
        // 深度优先搜索
        int len = rooms.size();
        HashSet<Integer> path = new HashSet<>();
        path.add(0);
        
        return mySol(rooms, len, 0, path);
    }

    private boolean mySol(List<List<Integer>> rooms, int len, int cur, HashSet<Integer> path) {
        // 递归终止条件
        if(path.size() == len) {
            // 该条路径下所有房间已经走过一遍
            return true;
        }
        // path.size() < len
        // 到达 cur 房间后，找该房间的钥匙集
        List<Integer> list = rooms.get(cur);
        int size = list.size();
        if(size == 0) {
            return false;
        }
        // size > 0
        for(int i = 0; i < size; i ++) {
            int next = list.get(i);
            if(path.contains(next)) {
                continue;
            } else {
                path.add(next);
                if(mySol(rooms, len, next, path)) {
                    return true; // 顺着 next 往下走，结果成功了
                }
                // path.remove(next); // 此时不需要回溯，因为统计的就是所有路径下走过的房间
            }
        }
        return false; // 当前房间下，下一个能走的房间均进行了尝试，前面不能 return true，此时就 return false
    }
}

---

输出 1

---

解法 2 - 广度优先

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        // 思路：
        // 横向搜索 - 广度优先
        // 借助 queue
        int amount = rooms.size();
        HashSet<Integer> set = new HashSet<>();
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(0);
        set.add(0);
        while(!queue.isEmpty()) {
            int len = queue.size(); // 当前层可探索房间数
            for(int i = 0; i < len; i ++) {
                int cur = queue.poll(); // 当前所处的房间号
                List<Integer> list = rooms.get(cur); // 在当前房间所能拿到的钥匙集
                for(int j = 0; j < list.size(); j ++) {
                    int next = list.get(j);
                    // System.out.println(cur + "   " + next);
                    if(!set.contains(next)) {
                        set.add(next);
                        if(set.size() == amount) {
                            return true; // 所有房间的钥匙已经集齐
                        }
                        queue.offer(next);
                    }
                }
            }
        }
        return false;
    }
}

---

输出