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

更新於: 2020-11-26

216 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告