मान लीजिए हमारे पास 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 लौटाएं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक खाली कतार बनाएं, और सभी कमरों के लिए एक विज़िटेड सरणी बनाएं और इसे false पर सेट करें
- queue := addRooms(rooms, 0, queue, visited)
- visited[0] := True
- जब कतार में कुछ तत्व हों
- queue := addRooms(rooms, queue[0], queue, visited)
- visited[queue[0]] को true चिह्नित करें,
- कतार से तत्व हटाएं
- जब विज़िटेड सरणी में सभी तत्व true हों तो true लौटाएं
- addRoom() rooms, index, queue और विज़िटेड सरणी लेगा, यह इस तरह होगा
- rooms[index] सरणी में i के लिए
- यदि i विज़िट नहीं किया गया है, तो i को कतार में डालें
- 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
