0841. 钥匙和房间

0841. 钥匙和房间 #

  • 标签:深度优先搜索、图
  • 难度:中等

题目大意 #

n 个房间,编号为 0 ~ n - 1,每个房间都有若干把钥匙,每把钥匙上都有一个编号,可以开启对应房间号的门。最初,除了 0 号房间外其他房间的门都是锁着的。

现在给定一个二维数组 roomsrooms[i][j] 表示第 i 个房间的第 j 把钥匙所能开启的房间号。

要求:判断是否能开启所有房间的门。如果能开启,则返回 True。否则返回 False

解题思路 #

x 号房间有 y 号房间的钥匙时,就可以认为我们可以通过 x 号房间去往 y 号房间。现在把 n 个房间看做是拥有 n 个节点的图,则上述关系可以看做是 xy 点之间有一条有向边。

那么问题就变为了给定一张有向图,从 0 节点开始出发,问是否能到达所有的节点。

我们可以先建图,然后可以从 0 节点开始,使用深度优先搜索的方式遍历整个图,并使用 set 集合来统计遍历到的节点个数。

最终判断一下遍历到的节点个数是否等于图的节点个数。如果等于,则返回 True,否则返回 False

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(x):
            visited.add(x)
            for key in rooms[x]:
                if key not in visited:
                    dfs(key)
        visited = set()
        dfs(0)
        return len(visited) == len(rooms)
本站总访问量  次  |  您是本站第  位访问者