পাইথনের নীচের ডানদিকে কোণায় পৌঁছাতে ন্যূনতম সংখ্যক কক্ষ খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি 2D গ্রিড আছে যা একটি গোলকধাঁধাকে উপস্থাপন করে যেখানে 0 হল খালি জায়গার জন্য এবং 1 হল প্রাচীর। আমরা গ্রিড[0, 0] এ শুরু করব, গ্রিডের নিচের ডানদিকের কোণে যেতে আমাদের ন্যূনতম সংখ্যক বর্গক্ষেত্র খুঁজে বের করতে হবে। যদি আমরা পৌঁছাতে না পারি, −1 ফিরে আসুন।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 5

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

• R :=গ্রিডের সারি গণনা, C :=গ্রিডের কলাম গণনা

• q :=[0, 0, 1] যখন A[0, 0] 1 হয় অন্যথায় একটি নতুন তালিকা

• A[0, 0] :=1

• প্রতিটি (r, c, d) এর জন্য q, do

  • যদি (r, c) একই হয় (R − 1, C − 1), তাহলে

    • d

      ফেরত দিন
  • 
    

    • প্রতিটি (x, y) এর জন্য [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1) ], do

      • যদি 0 থেকে R পরিসরে x এবং 0 থেকে C পরিসরে y এবং A[x, y] 0 এর সমান হয়, তাহলে

        • A[x, y] :=1

        • q

          এর শেষে সন্নিবেশ করুন (x, y, d + 1)

• ফিরুন −1

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

উদাহরণ

class Solution:
   def solve(self, A):
      R, C = len(A), len(A[0])
      q = [(0, 0, 1)] if not A[0][0] else []
      A[0][0] = 1
      for r, c, d in q:
         if (r, c) == (R − 1, C − 1):
            return d
         for x, y in [(r + 1, c), (r − 1, c), (r, c + 1), (r, c −1)]:
            if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
               A[x][y] = 1
               q.append((x, y, d + 1))
      return −1
ob = Solution()
grid = [
   [0, 0, 0],
   [1, 0, 0],
   [1, 0, 0]
]
print(ob.solve(grid))

ইনপুট

grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]

আউটপুট

5