Pythonで目的地に到達するために増加する高さの最小数を見つけるプログラム

M[r][c]がそのセルの高さを表す行列Mがあるとします。現在左上隅にいて、右下隅に移動したい場合。隣接するセルの高さが現在のセルの高さ以下である場合にのみ、隣接するセル（上、下、左、右）に移動できます。移動する前に任意の数のセルの高さを増やすことができるため、右下のセルに移動できるように、増やす必要のある最小の合計の高さを見つける必要があります。

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

次のパス[2、4、5、1]を使用して、高さをこの構成に変更できるため、出力は4になります-

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

INF：=無限大

• R、C：=行列の行番号、行列の列番号

• pq：=ヒープを使用して優先キューを作成し、それに[0、R-1、C-1、M [-1、-1]]を挿入します

• dist：=マップ

• dist [R-1、C-1、A [-1、-1]]：=0

• pqが空でない間、実行します

  • pqから1つの要素を削除し、それらをd、r、c、hに格納します

  • dist [r、c、h]

    • 次のイテレーションに行く

  • rとcが両方とも0の場合、

    • dを返す

  • [[r + 1、c]、[r、c + 1]、[r-1、c]、[r、c-1]]の各ペア（nr、nc）について、実行

    • 0 <=nr

      • d2

        • dist [nr、nc、h2]：=d2

        • [d2、nr、nc、h2]をpqに挿入します

理解を深めるために、次の実装を見てみましょう-

例

import collections
import heapq
class Solution:
   def solve(self, A):
      INF = float('inf')
      R, C = len(A), len(A[0])

      pq = [[0, R-1, C-1, A[-1][-1]]]
      dist = collections.defaultdict(lambda: INF)
      dist[R-1, C-1, A[-1][-1]] = 0
      while pq:
         d, r, c, h = heapq.heappop(pq)
         if dist[r, c, h] < d:
            continue
         if r == c == 0:
            return d
         for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
            if 0 <= nr < R and 0 <= nc < C:
               h2 = max(A[nr][nc], h)
               d2 = d + max(h2 - A[nr][nc], 0)
               if d2 < dist[nr, nc, h2]:
                  dist[nr, nc, h2] = d2
                  heapq.heappush(pq, [d2, nr, nc, h2])
ob = Solution()
matrix = [
[2, 4, 5],
[8, 6, 1]
]
print(ob.solve(matrix))

入力

[[2, 4, 5],[8, 6, 1]]

出力

4