আমরা পাইথনে সমস্ত রুম আনলক করতে পারি কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে রুম নামক তালিকার একটি তালিকা আছে। কক্ষের প্রতিটি সূচী i একটি রুম এবং রুম[i] অন্যান্য রুম খোলার জন্য বিভিন্ন কী প্রতিনিধিত্ব করে। রুম 0 খোলা আছে এবং আমরা সেই ঘরে আছি এবং অন্য প্রতিটি ঘর তালাবদ্ধ। আমরা খোলা ঘরের মধ্যে অবাধে চলাফেরা করতে পারি; আমরা প্রতিটি রুম খুলতে পারি কি না তা পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুটটি রুম =[[2, 0], [3], [1], []] এর মত হয়, তাহলে আউটপুট হবে True, যেহেতু আমরা রুম 0 থেকে শুরু করি এবং এর কী দিয়ে রুম 2 এ যেতে পারি। 2. রুম 2 থেকে আমরা 1 রুম এ যেতে পারি। তারপর, 3 রুম এর চাবি নিন এবং এটি খুলুন। তাই সব খুলে দেওয়া হয়।

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

• n :=কক্ষের আকার
• তৈরি :=একক উপাদান 0 সহ একটি তালিকা
• দেখেছি :=একটি নতুন সেট
• যখন প্রস্তুত খালি নয়, করুন
  • u :=প্রস্তুতের শেষ উপাদান এবং প্রস্তুত থেকে এটি মুছুন
  • আপনাকে দেখা হিসাবে চিহ্নিত করুন
  • রুমে প্রতিটি v এর জন্য[u], করুন
    • যদি v দেখা না যায়, তাহলে
      • তৈরি শেষে v ঢোকান
• সত্যে প্রত্যাবর্তন করুন যখন দেখার আকার 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