กุญแจและห้องใน Python

สมมติว่าเรามี N ห้อง และเริ่มที่ห้อง 0 ในแต่ละห้องมีหมายเลขที่แตกต่างกันใน 0, 1, 2, ..., N-1 และแต่ละห้องอาจมีกุญแจบางอันเพื่อเข้าถึงห้องถัดไป กล่าวอีกนัยหนึ่ง แต่ละห้อง i มีรายการกุญแจ rooms[i] และแต่ละกุญแจ rooms[i][j] เป็นจำนวนเต็มใน [0, 1, ..., N-1] โดยที่ N = จำนวนห้อง กุญแจ rooms[i][j] = v จะเปิดห้องหมายเลข v ดังนั้นถ้าอินพุตคือ [[1], [2], [3], []] ผลลัพธ์จะเป็น true มีจุดสำคัญดังนี้ −

• เริ่มต้น ห้องทั้งหมดถูกล็อก (ยกเว้นห้อง 0)
• เราสามารถเดินไป-กลับระหว่างห้องได้อย่างอิสระ
• ควรคืนค่า true ก็ต่อเมื่อเราสามารถเข้าทุกห้องได้

เราจะเริ่มจากห้อง 0 หยิบกุญแจ 1 ไปห้อง 1 หยิบกุญแจ 2 ไปห้อง 2 หยิบกุญแจ 3 หลังเยี่ยมห้อง 3 ถ้าห้องทั้งหมดถูกเยี่ยมแล้ว คืนค่า true

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

• สร้างคิวว่าง และสร้างอาร์เรย์ visited สำหรับทุกห้อง ตั้งค่าเป็น false
• queue := addRooms(rooms, 0, queue, visited)
• visited[0] := True
• while queue มีองค์ประกอบ
  • queue := addRooms(rooms, queue[0], queue, visited)
  • ตั้ง visited[queue[0]] เป็น true
  • ลบองค์ประกอบออกจาก queue
• คืนค่า true เมื่อทุกองค์ประกอบใน visited array เป็น true
• ฟังก์ชัน addRoom() จะรับ rooms, index, queue และ visited array จะทำงานดังนี้
  • for i ใน rooms[index] array
    • ถ้า i ยังไม่ได้เยี่ยม ให้เพิ่ม i เข้า queue
  • คืนค่า queue

ตัวอย่าง (Python)

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

class Solution(object):
    def canVisitAllRooms(self, rooms):
        queue = []
        visited = [False for i in rooms]
        queue = self.add_rooms(rooms, 0, queue, visited)
        visited[0] = True
        while len(queue) > 0:
            queue = self.add_rooms(rooms, queue[0], queue, visited)
            visited[queue[0]] = True
            queue.pop(0)
        return all(visited)

    def add_rooms(self, rooms, index, queue, visited):
        for i in rooms[index]:
            if not visited[i]:
                queue.append(i)
        return queue

ob1 = Solution()
print(ob1.canVisitAllRooms([[1], [2], [3], []]))

อินพุต

[[1],[2],[3],[]]

ผลลัพธ์

true