पायथन में चाबियां और कमरे

मान लीजिए कि हमारे पास N कमरे हैं और हम कमरा 0 से शुरू करते हैं। प्रत्येक कमरे में 0, 1, 2, ..., N-1 में एक अलग संख्या मौजूद है, और प्रत्येक कमरा हो सकता है अगले कमरे में जाने के लिए कुछ चाबियां हैं। तो दूसरे शब्दों में, प्रत्येक कमरे में मेरे पास चाबियों के कमरे की एक सूची है [i], और प्रत्येक कुंजी कमरे [i] [जे] [0, 1, ..., एन -1] में एक पूर्णांक है जहां एन =की संख्या कमरे। एक प्रमुख कमरा [i] [j] =v, यह संख्या v के साथ कमरा खोलता है इसलिए यदि इनपुट [1], [2], [3], []] है। तो आउटपुट सत्य होगा। कुछ और बिंदु हैं जिन्हें हमें ध्यान में रखना चाहिए -

• शुरुआत में, सभी कमरे बंद होने लगते हैं (कमरे 0 को छोड़कर)।
• हम स्वतंत्र रूप से कमरों के बीच आगे-पीछे चल सकते हैं।
• अगर हम हर कमरे में प्रवेश कर सकते हैं तो हमें सच लौटना चाहिए।

तो हम कमरा 0 से शुरू करेंगे और चाबी 1 को उठाएंगे, फिर कमरे 1 में जाएँ, 2 के लिए चाबी लें, फॉर्म रूम 2, 3 के लिए चाबी लें, 3 पर जाने के बाद, यदि सभी कमरे हैं दौरा किया, फिर सही लौटें।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक खाली कतार बनाएं, और सभी कमरों के लिए विज़िट की गई सरणी बनाएं और असत्य के रूप में सेट करें
• कतार:=AddRooms(कमरे, 0, कतार, देखी गई)
• विज़िट किया[0] :=Ture
• जबकि कतार में कुछ तत्व हैं
  • कतार:=AddRooms(कमरे, कतार[0], कतार, देखी गई)
  • भेजे गए [कतार[0]] को सही के रूप में चिह्नित करें,
  • तत्व को कतार से हटाएं
• सही लौटें, जब विज़िट किए गए सरणी में सभी तत्व सत्य हों
• AddRoom() कमरे, अनुक्रमणिका, कतार और विज़िट की गई सरणी लेगा, यह इस तरह होगा
• आई इन रूम्स [इंडेक्स] ऐरे के लिए
  • अगर मैं नहीं जाता हूं, तो मुझे कतार में डालें
• वापसी कतार

उदाहरण (पायथन)

एक बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -

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