Leetcode 841-钥匙和房间

有 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);
        }
    }
}

原文地址：https://blog.csdn.net/Helene1996/article/details/144348273

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！