用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))