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