Python에서 최대 최소값이 있는 경로

<시간/>

R개의 행과 C개의 열이 있는 정수의 행렬 A가 있다고 가정하고 [0,0]에서 시작하여 [R-1,C-1]에서 끝나는 경로의 최대 점수를 찾아야 합니다. 여기에서 스코어링 기술은 해당 경로의 최소값이 됩니다. 예를 들어, 경로 8 → 4 → 5 → 9의 값은 4입니다. 경로는 방문한 한 셀에서 방문하지 않은 이웃 셀로 4가지 기본 방향(북쪽, 동쪽, 서쪽, 남쪽) 중 하나로 몇 번 이동합니다. .

예를 들어 그리드가 다음과 같은 경우 -

5	4	5
1	2	6
7	4	6

주황색 셀이 경로가 됩니다. 출력은 4입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

r :=행 수 및 c :=열 수
ans :=A[0, 0] 및 A[r – 1, c – 1]의 최소값
A와 같은 순서의 방문이라는 행렬을 하나 만들고 FALSE로 채웁니다.
h :=튜플을 저장하는 목록(-A[0, 0], 0, 0)
h에서 힙 만들기
h가 비어 있지 않은 동안
- v, x, y :=힙에서 h를 삭제하고 세 개의 값을 저장
- x =r – 1이고 y :=c – 1이면 루프에서 나옵니다.
- ans :=ans의 최소값, A[x, y]
- 방문함[x, y] :=사실
- dy, 목록의 dx [(-1, 0), (1, 0), (0, 1), (0, -1)], do
  - a :=x + dx 및 b :=y + dy
  - 0 ~ r – 1 범위의 a 및 0 ~ c – 1 범위의 b 및 방문 [a, b]가 false인 경우
    - h를 사용하여 힙에 (-A[a, b], b) 삽입
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

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