โปรแกรมเช็คว่าปลดล็อคทุกห้องได้หรือเปล่าใน python

สมมติว่าเรามีรายชื่อห้องที่เรียกว่าห้อง แต่ละดัชนี i ในห้องแสดงถึงห้อง และห้อง[i] แสดงถึงคีย์ที่แตกต่างกันในการเปิดห้องอื่นๆ ห้อง 0 เปิดแล้วและเราอยู่ที่ห้องนั้นและห้องอื่น ๆ ทั้งหมดถูกล็อค เราสามารถย้ายได้อย่างอิสระระหว่างห้องที่เปิดอยู่ ต้องเช็คก่อนว่าเปิดทุกห้องหรือเปล่า

ดังนั้น ถ้า input เหมือนกับ rooms =[[2, 0], [3],[1],[]] ผลลัพธ์จะเป็น True เนื่องจากเราเริ่มจากห้อง 0 และสามารถไปที่ห้อง 2 ได้โดยใช้กุญแจ 2. จากห้องที่ 2 เราไปห้องที่ 1 แล้วเอากุญแจห้อง 3 เปิดออก ทุกคนก็เปิดออก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• n :=ขนาดห้อง
• พร้อม :=รายการที่มีองค์ประกอบเดียว 0
• เห็นแล้ว :=ชุดใหม่
• ถึงพร้อมไม่ว่างก็ทำ
  • u :=องค์ประกอบสุดท้ายของ ready และลบออกจาก ready
  • ทำเครื่องหมายว่าเห็นแล้ว
  • สำหรับแต่ละ v ในห้อง[u] ทำ
    • ถ้าไม่เห็น v แล้ว
      • ใส่ v ต่อท้าย ready
• คืนค่า จริง เมื่อขนาดของการเห็นเท่ากับ n มิฉะนั้น จะเป็นเท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

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