数据结构
网络
关系数据库管理系统 (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 次浏览
广告