सभी कमरों को अनलॉक किया जा सकता है या नहीं जांचने का पायथन प्रोग्राम

मान लीजिए हमारे पास 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 को seen के रूप में चिह्नित करें
  • प्रत्येक v के लिए rooms[u] में, करें
    • यदि v seen नहीं है, तो
      • v को ready के अंत में डालें
• सत्य लौटाएं जब seen का आकार 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