資料結構
網路
關係資料庫管理系統 (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 次瀏覽
