Pythonで最小値が最大のパス

R行とC列の整数の行列Aがあるとすると、[0,0]で始まり[R-1、C-1]で終わるパスの最大スコアを見つける必要があります。ここで、スコアリング手法はそのパスの最小値になります。たとえば、パス8→4→5→9の値は4です。パスは、4つの主要な方向（北、東、西、南）のいずれかで、1つの訪問済みセルから隣接する未訪問セルに数回移動します。 。

たとえば、グリッドが-

オレンジ色のセルがパスになります。出力は4です

これを解決するには、次の手順に従います-

• r：=行数およびc：=列数
• ans：=最小値のA [0、0]およびA [r – 1、c – 1]
• Aと同じ順序でvisitedと呼ばれる1つの行列を作成し、これをFALSEで埋めます
• h：=タプルを格納するリスト（-A [0、0]、0、0）
• hからヒープを作成する
• hが空でない間
  • v、x、y：=ヒープからhを削除し、3つの値を格納します
  • x =r – 1およびy：=c – 1の場合、ループから抜け出します
  • ans：=最小のans、A [x、y]
  • visited [x、y]：=true
  • dyの場合、リスト内のdx [（-1、0）、（1、0）、（0、1）、（0、-1）]、do
    • a：=x + dxおよびb：=y + dy
    • aが0〜r – 1の範囲にあり、bが0〜c – 1の範囲にあり、visited [a、b]がfalseの場合、
      • （-A [a、b]、a、b）をhでヒープに挿入します
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

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