用 Python 编写程序，以最小的努力寻找路径

pythonserver side programmingprogramming更新于 2025/11/30 3:24:17

假设我们有一个 m x n 阶的二维矩阵，称为高度。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。

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

r := 高度中的行数，c:= 高度中的列数
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] 为空字符串，则
  - 进行下一次迭代
- 对于 [[1,0],[-1,0],[0,1],[0,-1]] 中的每个 dx,dy，执行
  - 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]:= blank string

示例

让我们看看下面的实现以便更好地理解 −

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