Python 中具有最大最小值的路径

pythonserver side programmingprogramming更新于 2025/8/25 8:44:17

假设我们有一个包含 R 行和 C 列的整数矩阵 A,我们必须找到从 [0,0] 开始到 [R-1,C-1] 结束的路径的最大得分。这里的得分技术将是该路径中的最小值。例如,路径的值 8 → 4 → 5 → 9 是 4。路径会从一个访问过的单元格移动到 4 个基本方向(北、东、西、南)中的任何相邻未访问单元格一定次数。

例如,如果网格像 −

545
126
746

橙色单元格将是路径。输出为 4

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

  • r := 行数和 c := 列数
  • ans := A[0, 0] 和 A[r – 1, c – 中的最小值1]
  • 创建一个与 A 顺序相同的矩阵,称为 accessed,并用 FALSE 填充它
  • h := 一个列表,其中我们存储一个元组 (-A[0, 0], 0, 0)
  • 从 h 创建堆
  • 当 h 不为空时
    • v, x, y := 从堆中删除 h,并存储三个值
    • 如果 x = r – 1 且 y := c – 1,然后退出循环
    • ans := min of ans, A[x, y]
    • visited[x, y] := true
    • 对于列表 [(-1, 0), (1, 0), (0, 1), (0, -1)] 中的 dy, dx,执行
      • a := x + dx and b := y + dy
      • 如果 a 在 0 到 r – 1 的范围内且 b 在 0 到 c – 1 的范围内且 accessed[a, b] 为 false,
        • 将 (-A[a, b], a, b) 插入到带有 h 的堆中
  • 返回 ans

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

示例

import heapq
class Solution(object):
   def maximumMinimumPath(self, A):
      """
      :type A: List[List[int]]
      :rtype: int
      """
      r,c = len(A),len(A[0])
      ans = min(A[0][0],A[-1][-1])
      visited = [[False for i in range(c)] for j in range(r)]
      h = [(-A[0][0],0,0)]
      heapq.heapify(h)
      while h:
         # print(h)
         v,x,y = heapq.heappop(h)
         if x== r-1 and y == c-1:
            break
         ans = min(ans,A[x][y])
         visited[x][y]= True
         for dx,dy in {(-1,0),(1,0),(0,1),(0,-1)}:
            a,b = x+dx,y+dy
            if a>=0 and a<r and b>=0 and b<c and not visited[a][b]:
               heapq.heappush(h,(-A[a][b],a,b))
      return ans

输入

[[5,4,5],[1,2,6],[7,4,6]]

输出

4

相关文章


有用资源