钥匙和房间

LeetCode每日一题，841. Keys and Rooms

先看题目描述

大意就是给定一个二维数组 rooms，里面代表每个房间里存的钥匙，有相应钥匙就可以进入相应房间，一开始除了 0 号房间，其他房间都是锁上的，问是否可以进入所有房间

算法和思路

这题可以看作图的遍历问题，每个房间可以看作不同节点，房间里的钥匙就代表它的相邻节点，那么问题问的就是该图是否是个连通图，解决该题可以用 dfs深度优先搜索，也可以用 bfs广度优先搜索，我使用的是 dfs

数组 visited[] 中存储的是是否访问过房间的相应信息，visited[i] = 0，就代表没访问过 i 号房间；visited[i] > 0，就代表访问过 i 号房间。我们使用深度优先搜索的方式遍历整张图，并使用数组 visited 记录访问信息，以防止重复访问，最后通过 visited 来判断是否所有节点均被访问，以返回 true 或 false

算法源码

import java.util.*;

class Solution {
    private int[] visited;

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        visited = new int[rooms.size()];
        visited[0]++;
        visitRoom(0, rooms);
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == 0) return false;
        }
        return true;
    }

    public void visitRoom(int num, List<List<Integer>> rooms) {
        for (Integer key: rooms.get(num)) {
            if (visited[key] == 0) {
                visited[key]++;
                visitRoom(key, rooms);
            }
        }
    }
}