পাইথনে ম্যাট্রিক্সে ডেস্টিনেশন পৌঁছাতে ন্যূনতম উচ্চতা বৃদ্ধি খুঁজে বের করার প্রোগ্রাম

ধরা যাক M নামক একটি ম্যাট্রিক্স আছে যেখানে M[r][c] সেই কক্ষের উচ্চতা। উপরের বাম কোণ থেকে নিচের ডান কোণে যেতে হবে। সন্নিহিত কক্ষে (উপরে, নিচে, বামে, ডানে) যাওয়া যাবে শুধু যদি সেটির উচ্চতা বর্তমান কক্ষের উচ্চতার চেয়ে কম বা সমান হয়। যেকোনো কক্ষের উচ্চতা বর্ধিত করা যায়। ন্যূনতম মোট উচ্চতা বৃদ্ধি খুঁজে বের করতে হবে।

উদাহরণ ম্যাট্রিক্স হলে আউটপুট 4।

সমাধানের ধাপসমূহ

INF := infinity
R, C := সারি ও কলাম সংখ্যা
pq := হিপ-ভিত্তিক প্রায়োরিটি কিউ, [0, R-1, C-1, M[-1][-1]] ইনসার্ট করুন।
dist := ডিফল্ট ডিকশনারি (INF)
dist[R-1, C-1, A[-1][-1]] := 0
যখন pq খালি নয়: d, r, c, h = heapq.heappop(pq)

যদি dist[r,c,h] < d হয়, কন্টিনিউ করুন।
যদি r == c == 0 হয়, d ফেরত দিন।
প্রতিটি সন্নিহিত (nr, nc) এর জন্য: যদি বৈধ হয়, h2 = max(A[nr][nc], h), d2 = d + max(h2 - A[nr][nc], 0)। যদি d2 < dist[nr,nc,h2] হয়, আপডেট করুন এবং pq-এ পুশ করুন।

উদাহরণ কোড

import collections
import heapq
class Solution:
    def solve(self, A):
        INF = float('inf')
        R, C = len(A), len(A[0])
        pq = [[0, R-1, C-1, A[-1][-1]]]
        dist = collections.defaultdict(lambda: INF)
        dist[R-1, C-1, A[-1][-1]] = 0
        while pq:
            d, r, c, h = heapq.heappop(pq)
            if dist[r, c, h] < d:
                continue
            if r == c == 0:
                return d
            for nr, nc in [[r+1, c], [r, c+1], [r-1, c], [r, c-1]]:
                if 0 <= nr < R and 0 <= nc < C:
                    h2 = max(A[nr][nc], h)
                    d2 = d + max(h2 - A[nr][nc], 0)
                    if d2 < dist[nr, nc, h2]:
                        dist[nr, nc, h2] = d2
                        heapq.heappush(pq, [d2, nr, nc, h2])

ob = Solution()
matrix = [
    [2, 4, 5],
    [8, 6, 1]
]
print(ob.solve(matrix))

ইনপুট

[[2, 4, 5],[8, 6, 1]]