Pythonで最小限の労力でパスを見つけるプログラム

高さと呼ばれる次数mxnの2D行列があるとします。 heights [i] [j]は、セル（i、j）の高さを表します。 （0、0）セルにいる場合は、右下のセル（m-1、n-1）に移動します。上、下、左、右に移動でき、最小限の労力でルートを見つけたいと考えています。この問題では、ルートの努力は、ルートの2つの連続するセル間の高さの最大絶対差です。最後に、目的地までの移動に必要な最小限の労力を見つける必要があります。

したがって、入力が次のような場合

ルートが[2,3,4,5,6]であるため、出力は1になります。連続するセルでは、最大絶対差が1になります。

これを解決するには、次の手順に従います-

• r：=高さの行数、c：=高さの列数
• queue：=キューは最初にタプル（0,0,0）を格納します
• キューが空でないときに、実行します
  • cur：=キューの最初のアイテムで、キューから削除します
  • c_eff：=cur [0]
  • x：=cur [1]
  • y：=cur [2]
  • xがr-1と同じで、yがc-1と同じ場合、
    • return c_eff
  • heights [x、y]が空白の文字列の場合、
    • 次の反復に進む
  • [[1,0]、[-1,0]、[0,1]、[0、-1]]の各dx、dyについて、実行
    • newx：=x + dx
    • newy：=y + dy
    • 0 <=newx
    • eff：=c_effと|heights [newx、newy]の最大値-heights [x、y] |
    • タプル（eff、newx、newy）をキューに挿入します
• heights [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]]

出力

1