পাইথনে কী এবং রুম সমস্যা সমাধান

মনে করুন N সংখ্যক রুম আছে এবং আমরা রুম ০-এ শুরু করি। প্রতিটি রুমে ০, ১, ২, ..., N-1 পর্যন্ত একটি স্বতন্ত্র নম্বর থাকে, এবং প্রতিটি রুমে পরবর্তী রুমে যেতে কিছু কী থাকতে পারে। অর্থাৎ, প্রতিটি রুম i-র একটি কী তালিকা rooms[i] আছে, এবং প্রতিটি কী rooms[i][j] হল [০, ১, ..., N-1] 범위에 있는 একটি পূর্ণসংখ্যা যেখানে N = রুমের সংখ্যা। একটি কী rooms[i][j] = v, অর্থাৎ এটি v নম্বরের রুম খোলে। তাই যদি ইনপুট হয় [[1], [2], [3], []], তবে আউটপুট হবে true। আরও কিছু পয়েন্ট মনে রাখতে হবে:

• প্রাথমিকভাবে, সমস্ত রুম লক করা থাকে (রুম ০ বাদে)।
• আমরা রুমগুলোতে বাধামুক্ত আবাজাওহা করতে পারি।
• আমাদের true রিটার্ন করতে হবে যদি এবং কেবল যদি আমরা সব রুমে প্রবেশ করতে পারি।

তাই আমরা রুম ০ থেকে শুরু করব এবং কী ১ নিব, তারপর রুম ১-এ যাব, সেখান থেকে ২-এর কী নিব, রুম ২ থেকে ৩-এর কী নিব, রুম ৩ ভিজিট করার পর যদি সব রুম ভিজিট হয়ে যায়, তবে true রিটার্ন করব।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

• একটি খালি কিউ তৈরি করুন, এবং সব রুমের জন্য একটি visited অ্যারে তৈরি করে false সেট করুন
• queue := addRooms(rooms, 0, queue, visited)
• visited[0] := True
• যখন কিউতে উপাদান থাকে
  • queue := addRooms(rooms, queue[0], queue, visited)
  • visited[queue[0]] true চিহ্নিত করুন,
  • কিউ থেকে উপাদানটি মুছে দিন
• যখন visited অ্যারেতে সব উপাদান true হয়, true রিটার্ন করুন
• addRoom() rooms, index, queue এবং visited অ্যারে নেবে, এটি নিচের মতো হবে
• rooms[index] অ্যারেতে i-এর জন্য
  • যদি i ভিজিট করা না থাকে, তবে i কিউতে ইনসার্ট করুন
• queue রিটার্ন করুন

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

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বুঝতে:

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