查找在Python中给定两个位置提取金的最低成本的程序

假设我们有一个二维矩阵和一些其他值，例如row，col，erow0，eco0，erow1和ecol1。如果我们当前的位置是矩阵[row，col]，并且我们要提取矩阵[erow0，ecol0]和矩阵[erow1，ecol1]处的黄金。我们可以上下左右移动，但是当我们在一个像元(r,c)时，我们必须支付成本矩阵[r，c]，尽管如果我们不止一次降落在一个像元上，则不会需要再次为该单元支付费用。我们必须找到在两个地点提取黄金的最低成本。

所以，如果输入像

row = 0，col = 0，erow0 = 0，ecol0 = 3，erow1 = 2，ecol1 = 2，则输出将为8，因为我们位于(0,0)并想从位置（0， 3）和(2,2)。因此，首先通过三个步骤从(0,0)移至(0,3)，然后返回(0,0)，然后按照标记的1单元格移至(2,2)。

例  

让我们看下面的实现以更好地理解-

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