有 n 个房间,房间按从 0 到 n - 1 编号。最初,除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而,你不能在没有获得钥匙的时候进入锁住的房间。
当你进入一个房间,你可能会在里面找到一套 不同的钥匙,每把钥匙上都有对应的房间号,即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true,否则返回 false。
题解
当 x 号房间中有 y 号房间的钥匙时,我们就可以从 x 号房间去往 y 号房间。如果我们将这 n 个房间看成有向图中的 n 个节点,那么上述关系就可以看作是图中的 x 号点到 y 号点的一条有向边。
这样一来,问题就变成了给定一张有向图,询问从 0 号节点出发是否能够到达所有的节点
class Solution {//用来记录已经走过了哪些房间(节点)boolean[] visited;//用来记录一共访问过了多少个房间int count=0;public boolean canVisitAllRooms(List<List<Integer>> rooms) {visited= new boolean[rooms.size()];dfs(rooms,0);return count==rooms.size();}//x:当前访问到的房间private void dfs(List<List<Integer>> rooms, int x){visited[x]=true;//可以访问到的房间数++count++;//依次访问x房间可以访问到的房间列表for(int num:rooms.get(x)){if(!visited[num]) dfs(rooms,num);}}
}