Pythonの特定の2つの場所で金を受け取るための最小コストを見つけるためのプログラム

2d行列と、row、col、erow0、ecol0、erow1、ecol1などの他の値があるとします。現在の位置が行列[row、col]で、行列[erow0、ecol0]と行列[erow1、ecol1]にある金をピックアップしたい場合。上下左右に移動できますが、セル（r、c）にいるときは、コストマトリックス[r、c]を支払う必要があります。ただし、セルに2回以上着地した場合は、支払いません。そのセルの費用を再度支払う必要があります。両方の場所で金を受け取るための最小コストを見つける必要があります。

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

row =0、col =0、erow0 =0、ecol0 =3、erow1 =2、ecol1 =2の場合、出力は8になります。これは、（0、0）にあり、場所（0、 3）および（2、2）。したがって、最初に（0、0）から（0、3）に3ステップ移動し、次に（0,0）に戻り、次にマークされた1つのセルに従って（2、2）に移動します。

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

• 関数is_valid（）を定義します。これにはx、yが必要です

• xとyが行列の範囲内にある場合はtrueを返し、そうでない場合はfalseを返します

• 関数min_cost（）を定義します。これにはsx、syが必要です

• heap：=アイテムを含むヒープ（matrix [sx、sy]、sx、sy）

• dists：=与えられた行列と同じサイズの行列で、infで埋める

• dists [sx、sy]：=matrix [sx、sy]

• ヒープが空でない間は、実行してください

  • （cost、x、y）：=ヒープの最初の要素とヒープから最初の要素を削除する

  • [（x、y --1）、（x + 1、y）、（x -1、y）、（x、y + 1）]の各ペア（nx、ny）に対して、実行

    • is_valid（nx、ny）およびmatrix [nx、ny] + cost

      • エッジ：=マトリックス[nx、ny]

      • dists [nx、ny]：=エッジ+コスト

      • （エッジ+コスト、nx、ny）をヒープに挿入します

• 戻り値

• メインの方法から、次のようにします-

• res：=inf

• a：=min_cost（row、col）、b：=min_cost（erow0、ecol0）、c：=min_cost（erow1、ecol1）

• 0から行列の行数までの範囲のiについては、次のようにします

  • 0から行列の列数までの範囲のjについては、次のようにします

    • res：=最小のresおよび（a [i、j] + b [i、j] + c [i、j]-2 * matrix [i、j]）

• 解像度を返す

例

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

import heapq
import math
class Solution:
   def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):
      def is_valid(x, y):
         return x >= 0 and y >= 0 and x < len(matrix) and y < len(matrix[0])
      def min_cost(sx, sy):
         heap = [(matrix[sx][sy], sx, sy)]
         dists = [[math.inf] * len(matrix[0]) for _ in range(len(matrix))]
         dists[sx][sy] = matrix[sx][sy]
         while heap:
            cost, x, y = heapq.heappop(heap)
            for nx, ny in [(x, y - 1), (x + 1, y), (x - 1, y), (x, y + 1)]:
               if is_valid(nx, ny) and matrix[nx][ny] + cost < dists[nx][ny]:
                  edge = matrix[nx][ny]
                  dists[nx][ny] = edge + cost
                  heapq.heappush(heap, (edge + cost, nx, ny))
         return dists
      res = math.inf
      a, b, c = min_cost(row, col), min_cost(erow0, ecol0), min_cost(erow1, ecol1)
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            res = min(res, a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j])
      return res
ob = Solution()
matrix = [
   [1, 1, 1, 1, 1],
   [1, 10, 10, 10, 10],
   [1, 1, 1, 10, 10]
]
row = 0
col = 0
erow0 = 0
ecol0 = 3
erow1 = 2
ecol1 = 2
print(ob.solve(matrix, row, col, erow0, ecol0, erow1, ecol1))

入力

[ [1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10]
], 0, 0, 0, 3, 2, 2

出力

8