用Python查找最小代价路径的程序
假设我们有一个称为height的m×n的2D矩阵。heights[i][j]表示单元格(i,j)的高度。如果我们在单元格(0,0)处,我们想要前往右下角的单元格(m−1,n−1)。我们可以向上、向下、向左或向右移动,我们希望找到需要最小代价的路径。在这个问题中,路径的代价是路径中两个连续单元格之间高度差的最大绝对值。因此,最后我们需要找到到达目的地所需的最小代价。
如果输入如下:
2 | 3 | 4 |
---|---|---|
4 | 9 | 5 |
6 | 4 | 6 |
那么输出将为1,因为路线[2,3,4,5,6]在连续单元格中的最大绝对值差为1。
为了解决问题,我们将遵循以下步骤:
- 将行数与高度中的列数、列数分配给c。
- 一个初始为tup(0,0,0)的队列。
- 当队列不为空时,执行以下操作:
- cur:队列中的第一个项目,并从队列中删除。
- c_eff:cur[0]
- x:cur[1]
- y:cur[2]
- 如果x等于r-1且y等于c-1,则:
- 返回c_eff。
- 如果heights[x, y]是空字符串,则:
- 转到下一次迭代。
- 对于每个dx,dy,都在[[1,0],[-1,0],[0,1],[0,-1]]中执行以下操作:
- newx:x + dx
- newy:y + dy
- 如果0 <= newx
- eff:c_eff和|heights[newx,newy] – heights[x,y]|的最大值。
- 将tup(eff,newx,newy)插入队列中。
- heights[x,y]:空字符串。
示例
下面是对这一问题的更好理解的实现:
import heapq
def solve(heights):
r,c=len(heights),len(heights[0])
queue=[(0,0,0)]
while queue:
cur=heapq.heappop(queue)
c_eff=cur[0]
x=cur[1]
y=cur[2]
if x==r-1 and y==c-1:
return c_eff
if heights[x][y]=="":
continue
for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
newx=x+dx
newy=y+dy
if 0<newx<r and 0<=newy<c and heights[newx][newy]!="":
eff = max(c_eff, abs(heights[newx][newy] - heights[x][y]))
heapq.heappush(queue,(eff, newx, newy))
heights[x][y]=""
matrix = [[2,3,4],[4,9,5],[6,4,6]]
print(solve(matrix))
输入
[[2,3,4],[4,9,5],[6,4,6]]
输出
1