資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：查詢達到目標所需增加的最小高度
假設我們有一個矩陣 M，其中 M[r][c] 代表該單元格的高度。如果我們當前位於左上角，並想移動到右下角。我們只能移動到相鄰單元格（上、下、左、右），前提是該相鄰單元格的高度小於或等於當前單元格的高度。我們可以在移動前增加任意數量單元格的高度，因此我們必須找到需要增加的最小總高度，以便能夠到達右下角單元格。
因此，如果輸入如下所示：
| 2 | 4 | 5 |
| 8 | 6 | 1 |
則輸出將為 4，因為我們可以選擇以下路徑 [2, 4, 5, 1] 並將高度更改為此配置：
| 5 | 5 | 5 |
| 8 | 6 | 1 |
為了解決這個問題，我們將遵循以下步驟：
INF := 無窮大
R, C := 矩陣的行數，矩陣的列數
pq := 使用堆建立一個優先順序佇列，並將 [0, R-1, C-1, M[-1, -1]] 插入其中
dist := 一個對映
dist[R-1, C-1, A[-1, -1]] := 0
當 pq 不為空時，執行以下操作：
從 pq 中刪除一個元素並將其儲存到 d、r、c、h 中
如果 dist[r, c, h] < d，則
進行下一次迭代
如果 r 和 c 都為 0，則
返回 d
對於 [[r+1, c], [r, c+1], [r-1, c], [r, c-1]] 中的每個對 (nr, nc)，執行以下操作：
如果 0 <= nr < R 且 0 <= nc < C，則
如果 d2 < dist[nr, nc, h2]，則
dist[nr, nc, h2] := d2
將 [d2, nr, nc, h2] 插入 pq
讓我們看看下面的實現以更好地理解：
示例
import collections
import heapq
class Solution:
def solve(self, A):
INF = float('inf')
R, C = len(A), len(A[0])
pq = [[0, R-1, C-1, A[-1][-1]]]
dist = collections.defaultdict(lambda: INF)
dist[R-1, C-1, A[-1][-1]] = 0
while pq:
d, r, c, h = heapq.heappop(pq)
if dist[r, c, h] < d:
continue
if r == c == 0:
return d
for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
if 0 <= nr < R and 0 <= nc < C:
h2 = max(A[nr][nc], h)
d2 = d + max(h2 - A[nr][nc], 0)
if d2 < dist[nr, nc, h2]:
dist[nr, nc, h2] = d2
heapq.heappush(pq, [d2, nr, nc, h2])
ob = Solution()
matrix = [
[2, 4, 5],
[8, 6, 1]
]
print(ob.solve(matrix))輸入
[[2, 4, 5],[8, 6, 1]]
輸出
4
更新於：2020年10月8日
146 次瀏覽
廣告