পাইথনে পাথ উইথ ম্যাক্সিমাম মিনিমাম ভ্যালু

মনে করুন একটি ম্যাট্রিক্স A আছে R রো এবং C কলামের সাথে। আমাদের [0,0] থেকে [R-1, C-1] পর্যন্ত পাথে যাওয়ার ম্যাক্সিমাম স্কোর বের করতে হবে। এখানে স্কোরিং টেকনিক হলো সেই পাথে থাকা ন্যূনতম ভ্যালু। উদাহরণস্বরূপ, পাথ 8 → 4 → 5 → 9-এর ভ্যালু হলো 4। একটি পাথ ৪ কার্ডিনাল ডিরেকশন (উত্তর, পূর্ব, পশ্চিম, দক্ষিণ) এ যেকোনো অনভিজিটেড নেighbouring সেলে যেতে পারে।

গ্রিড যদি নিচের মতো হয়:

5	4	5
1	2	6
7	4	6

অরেঞ্জ কэлগুলোই পাথ। আউটপুট 4।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (Dijkstra-সদৃশ BFS + Max-Heap / Priority Queue):

r := rows, c := cols
ans := min(A[0][0], A[r-1][c-1])
visited ম্যাট্রিক্স A-র অর্ডারের, False দিয়ে পূরণ।
h := [(-A[0][0], 0, 0)] (নেগেটিভ ভ্যালু দিয়ে ম্যাক্স-হিপ সিমুলেট)
heapify(h)
while h not empty:
- v, x, y = heappop(h)
- যদি x == r-1 and y == c-1, তবে ব্রেক।
- ans = min(ans, A[x][y])
- visited[x][y] = True
- for dx, dy in [(-1,0),(1,0),(0,1),(0,-1)]:
  - a = x+dx, b = y+dy
  - যদি a,b ভ্যালিড এবং not visited[a][b], তবে heappush(h, (-A[a][b], a, b))
return 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:
            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]]