Python 程序检查是否可以解锁所有房间

假设我们有一个称为 rooms 的列表列表。rooms 中的每个索引 i 代表一个房间，rooms[i] 代表打开其他房间的不同钥匙。房间 0 是打开的，我们在这个房间里，其他所有房间都锁着。我们可以在打开的房间之间自由移动；我们必须检查是否可以打开每个房间。

因此，如果输入类似于 rooms = [[2, 0], [3],[1],[]]，则输出将为 True，因为我们从房间 0 开始，可以使用其钥匙 2 转到房间 2。从房间 2，我们可以转到房间 1。然后，获取房间 3 的钥匙并打开它。因此，所有房间都打开了。

要解决此问题，我们将遵循以下步骤

• n := rooms 的大小
• ready := 一个包含单个元素 0 的列表
• seen := 一个新的集合
• 当 ready 不为空时，执行以下操作
  • u := ready 的最后一个元素，并将其从 ready 中删除
  • 将 u 标记为已查看
  • 对于 rooms[u] 中的每个 v，执行以下操作
    • 如果 v 未被查看，则
      • 将 v 插入到 ready 的末尾
• 当 seen 的大小与 n 相同时返回 true，否则返回 false。

让我们查看以下实现以获得更好的理解

示例

实时演示

class Solution:
   def solve(self, rooms):
      n = len(rooms)

      ready = [0]
      seen = set()

      while ready:
         u = ready.pop()
         seen.add(u)

         for v in rooms[u]:
            if v not in seen:
               ready.append(v)

      return len(seen) == n

ob = Solution()
rooms = [
   [2, 0],
   [3],
   [1],
   []
]
print(ob.solve(rooms))

输入

rooms = [[2, 0],[3],[1],[]]

输出

True

Arnab Chakraborty

更新于: 2020-11-26

216 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习