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

假设我们有一个具有R行和C列的整数矩阵A，我们必须找到从[0,0]开始并在[R-1，C-1]结束的路径的最大分数。此处，计分技术将是该路径中的最小值。例如，路径8→4→5→9的值为4。路径从一个访问的单元沿4个基本方向之一（北，东，西，南）移动了若干次。 。

例如，如果网格像-

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

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

• r：=行数，c：=列数

• ans：= A [0，0]和A [r – 1，c – 1]的最小值

• 制作一个称为A的顺序访问的矩阵，并用FALSE填充

• h：=一个列表，我们在其中存储一个元组（-A [0，0]，0，0）

• 从h堆

• 当h不为空时

• a：= x + dx和b：= y + dy

• 如果a在0到r – 1的范围内，而b在0到c – 1的范围内，并且visited [a，b]为假，

• 用h将（-A [a，b]，a，b）插入堆

• v，x，y：=从堆中删除h，并存储三个值

• 如果x = r – 1且y：= c – 1，则从循环中出来

• ans：= ans的最小值，A [x，y]

• Visited [x，y]：= true

• 对于列表[(-1,0)，(1,0)，(0,1)，(0,-1)]中的dy，dx

• 返回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