查找在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