পাইথনে কী এবং রুম

ধরুন আমাদের N রুম আছে এবং আমরা 0 রুমে শুরু করি। প্রতিটি রুমে 0, 1, 2, ..., N-1-এ একটি স্বতন্ত্র সংখ্যা রয়েছে এবং প্রতিটি রুম হতে পারে পাশের ঘরে প্রবেশ করার জন্য কিছু চাবি আছে। সুতরাং অন্য কথায়, প্রতিটি রুম i এর কী রুমগুলির একটি তালিকা রয়েছে[i], এবং প্রতিটি কী রুম [i][j] হল একটি পূর্ণসংখ্যা [0, 1, ..., N-1] যেখানে N =সংখ্যা কক্ষ একটি কী রুম[i][j] =v, এটি v নম্বর দিয়ে রুম খোলে তাই যদি ইনপুটটি [[1], [2], [3], []] হয়। তাহলে আউটপুট সত্য হবে। আরও কয়েকটি পয়েন্ট আছে যা আমাদের মনে রাখা উচিত -

• প্রাথমিকভাবে, সমস্ত রুম লক করা শুরু হয় (রুম 0 বাদে)।
• আমরা অবাধে কক্ষগুলির মধ্যে পিছনে পিছনে হাঁটতে পারি৷
• যদি আমরা প্রতিটি ঘরে প্রবেশ করতে পারি তবেই আমাদের সত্যে ফিরে আসা উচিত৷

সুতরাং আমরা 0 রুম থেকে শুরু করব এবং 1 চাবি তুলব, তারপর 1 কক্ষে যাব, 2-এর জন্য চাবি নেব, ফর্ম রুম 2-এর জন্য চাবি নেব, 3-এর জন্য চাবি নিব, 3-তে যাওয়ার পর, যদি সমস্ত কক্ষ হয় পরিদর্শন, তারপর সত্য ফিরে.

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি খালি সারি তৈরি করুন এবং সমস্ত কক্ষের জন্য একটি পরিদর্শন অ্যারে তৈরি করুন এবং মিথ্যা হিসাবে সেট করুন
• সারি :=অ্যাডরুম (রুম, 0, সারি, পরিদর্শন করা)
• পরিদর্শন করেছেন[0] :=তুর
• যদিও কিউতে কিছু উপাদান থাকে
  • সারি :=অ্যাডরুম (রুম, সারি[0], সারি, পরিদর্শন করা)
  • ভিজিট করা[সারি[0]]কে সত্য হিসেবে চিহ্নিত করুন,
  • সারি থেকে উপাদান মুছুন
• সত্য ফেরত দিন, যখন পরিদর্শন করা অ্যারেতে সমস্ত উপাদান সত্য হয়
• addRoom() রুম, সূচী, সারি এবং পরিদর্শন করা অ্যারে নিয়ে যাবে, এটি এরকম হবে
• রুমে [index] অ্যারে
  এর জন্য
  • যদি আমি পরিদর্শন না করি, তাহলে আমি সারিতে ঢোকান
• রিটার্ন সারি

উদাহরণ(পাইথন)

আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −

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