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

假设我们有一个2D矩阵和一些其他值，例如行，列，erow0，ecol0，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）。

为了解决这个问题，我们将按照以下步骤进行 –

• 定义一个函数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]

• while heap不为空，做到

  • (cost，x，y)：=堆的第一个元素并从堆中删除第一个元素

  • 对于[(x，y-1)，(x + 1，y)，(x-1，y)，(x，y + 1)]中的每对（nx，ny），做

    • 如果is_valid（nx，ny）并且矩阵[nx，ny] + cost < dists [nx，ny]不为零，则

    • 边缘：=矩阵[nx，ny]

    • dists [nx，ny]：= edge + cost

    • 将（edge + cost，nx，ny）插入堆中

  • 返回dists

  • 从主方法执行以下操作 –

  • 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]）的最小值

  • 返回res

实例

让我们看一下以下实现以更好地理解 –

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