数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找在给定两个位置收集黄金的最低成本
假设我们有一个二维矩阵以及其他一些值，例如row、col、erow0、ecol0、erow1和ecol1。如果我们当前的位置是矩阵[row, col]，并且我们想要拾取位于矩阵[erow0, ecol0]和矩阵[erow1, ecol1]的黄金。我们可以向上、向下、向左和向右移动，但是当我们位于单元格(r, c)时，我们必须支付成本矩阵[r, c]，尽管如果我们多次到达同一个单元格，我们不需要再次支付该单元格的成本。我们必须找到在两个位置拾取黄金的最低成本。
因此，如果输入如下所示：
| 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，则输出将为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 := 一个与给定矩阵大小相同的矩阵，并填充无穷大。
dists[sx, sy] := matrix[sx, sy]
当堆heap不为空时，执行以下操作：
(cost, x, y) := 堆heap的第一个元素，并从堆heap中删除第一个元素。
对于[(x, y - 1) ,(x + 1, y) ,(x - 1, y) ,(x, y + 1)]中的每个对(nx, ny)，执行以下操作：
如果`is_valid(nx, ny)`且`matrix[nx, ny] + cost < dists[nx, ny]`非零，则：
edge := matrix[nx, ny]
dists[nx, ny] := edge + cost
将(edge + cost, nx, ny)插入堆heap。
返回dists。
从主方法执行以下操作：
res := 无穷大
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
116 次浏览
