পাইথনে ন্যূনতম প্রচেষ্টার সাথে পথ খোঁজার প্রোগ্রাম

ধরুন আমাদের m x n এর 2D ম্যাট্রিক্স আছে যার নাম উচ্চতা। উচ্চতা [i][j] ঘরের উচ্চতা (i, j) প্রতিনিধিত্ব করে। যদি আমরা (0, 0) ঘরে থাকি তবে আমরা নীচে-ডান ঘরে ভ্রমণ করতে চাই, (m-1, n-1)। আমরা উপরে, নীচে, বামে বা ডানদিকে যেতে পারি এবং আমরা এমন একটি রুট খুঁজে পেতে চাই যার জন্য সর্বনিম্ন প্রচেষ্টা প্রয়োজন। এই সমস্যায় রুট প্রচেষ্টা হল রুটের পরপর দুটি কক্ষের মধ্যে উচ্চতার সর্বোচ্চ পরম পার্থক্য। তাই অবশেষে, আমাদের গন্তব্যে ভ্রমণের জন্য প্রয়োজনীয় ন্যূনতম প্রচেষ্টা খুঁজে বের করতে হবে।

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

2	3	4
4	9	5
6	4	6

তাহলে আউটপুট হবে 1 কারণ রুটটি [2,3,4,5,6] পরপর কক্ষে সর্বোচ্চ 1 এর পরম পার্থক্য রয়েছে।

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

r :=উচ্চতায় সারির সংখ্যা, c:=উচ্চতায় কলামের সংখ্যা
সারি:=একটি সারি প্রাথমিকভাবে একটি টিপল (0,0,0) সংরক্ষণ করে
যখন সারি খালি না থাকে, কর
- cur:=সারির প্রথম আইটেম এবং সারি থেকে মুছে ফেলুন
- c_eff:=cur[0]
- x:=cur[1]
- y:=cur[2]
- যদি x r-1 এর মত হয় এবং y c-1 এর মত হয়, তাহলে
  - c_eff ফেরত
- যদি উচ্চতা[x, y] একটি ফাঁকা স্ট্রিং হয়, তাহলে
  - পরবর্তী পুনরাবৃত্তির জন্য যান
- প্রতিটি dx-এর জন্য, [[1,0],[-1,0],[0,1],[0,-1]], dয় করুন
  - newx :=x+dx
  - নতুন :=y+dy
  - যদি 0 <=newx
  - eff :=সর্বাধিক c_eff এবং |উচ্চতা[newx,newy] - উচ্চতা[x,y]|
  - টিপল (eff, newx, newy) সারিতে ঢোকান
উচ্চতা[x, y]:=ফাঁকা স্ট্রিং

উদাহরণ

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

import heapq
def solve(heights):
   r,c=len(heights),len(heights[0])
   queue=[(0,0,0)]

   while queue:

      cur=heapq.heappop(queue)
      c_eff=cur[0]
      x=cur[1]
      y=cur[2]

      if x==r-1 and y==c-1:
         return c_eff

      if heights[x][y]=="":
         continue

      for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
         newx=x+dx
         newy=y+dy
         if 0<=newx<r and 0<=newy<c and heights[newx][newy]!="":

            eff = max(c_eff, abs(heights[newx][newy] - heights[x][y]))
            heapq.heappush(queue,(eff, newx, newy))

      heights[x][y]=""

matrix = [[2,3,4],[4,9,5],[6,4,6]]
print(solve(matrix))

ইনপুট

[[2,3,4],[4,9,5],[6,4,6]]