पायथन में न्यूनतम प्रयास के साथ पथ खोजने का कार्यक्रम

मान लीजिए कि हमारे पास 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:=वक्र[1]
- y:=cur[2]
- यदि x, r-1 के समान है और y, c-1 के समान है, तो
  - c_eff लौटाएं
- अगर हाइट्स[x, y] एक खाली स्ट्रिंग है, तो
  - अगले पुनरावृत्ति के लिए जाएं
- प्रत्येक dx के लिए, डाई इन [[1,0],[-1,0],[0,1],[0,-1]], do
  - newx :=x+dx
  - नया :=y+dy
  - यदि 0 <=newx
  - eff :=अधिकतम c_eff और |heights[newx,newy] - heights[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]]