Python程序：查找最小努力路径

假设我们有一个m x n阶的二维矩阵height。heights[i][j]表示单元格(i, j)的高度。如果我们在(0, 0)单元格，我们想要移动到右下单元格(m-1, n-1)。我们可以向上、下、左或右移动，我们希望找到一条需要最小努力的路线。在这个问题中，路线的努力是路线中两个连续单元格之间高度的最大绝对差。因此，最终我们需要找到到达目的地的最小努力。

因此，如果输入如下：

234
495
646

则输出为1，因为路线[2,3,4,5,6]中连续单元格的最大绝对差为1。

为了解决这个问题，我们将遵循以下步骤：

  • r := heights的行数，c:= heights的列数
  • queue:= 一个队列，最初存储一个元组(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 in [[1,0],[-1,0],[0,1],[0,-1]]，执行以下操作：
      • newx := x+dx
      • newy := y+dy
      • 如果0 <= newx < r 且 0 <= newy < c 且 heights[newx, newy]不等于空字符串，则
        • eff := c_eff和|heights[newx,newy] - heights[x,y]|中的最大值
        • 将元组(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

更新于：2021年10月5日

342 次浏览

开启您的职业生涯

完成课程后获得认证

开始
广告