পাইথনে দুটি লোকেশনে সোনা সংগ্রহ করার ন্যূনতম খরচ বের করার প্রোগ্রাম

ধরুন আমাদের একটি ২D ম্যাট্রিক্স এবং কিছু মান row, col, erow0, ecol0, erow1, ecol1 দেওয়া আছে। বর্তমান অবস্থান matrix[row][col] এবং আমরা দুটি লোকেশন matrix[erow0][ecol0] এবং matrix[erow1][ecol1]-এ সোনা সংগ্রহ করতে চাই। আমরা উপরে, নিচে, বামে, ডানে যেতে পারি। যেকোনো সেল (r, c)-এ হলে খরচ matrix[r][c] দিতে হয়, কিন্তু একই সেলে একাধিকবার যাওয়ায় খরচ একবারই দিতে হয়। দুটি লোকেশনে সোনা সংগ্রহ করার ন্যূনতম খরচ বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট ম্যাট্রিক্স:

1	1	1	1	1
1	10	10	10	10
1	1	1	10	10

row = 0, col = 0, erow0 = 0, ecol0 = 3, erow1 = 2, ecol1 = 2 হলে আউটপুট হবে 8।

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

is_valid(x, y) ফাংশন: x, y ম্যাট্রিক্সের রেঞ্জে আছে কিনা তা যাচাই করুন
min_cost(sx, sy) ফাংশন (ডিজক্সট্রা অ্যালগরিদম):
- heap := [(matrix[sx][sy], sx, sy)]
- dists := ম্যাট্রিক্সের আকারের একটি ম্যাট্রিক্স, সবগুলো inf দিয়ে ভরা
- dists[sx][sy] = matrix[sx][sy]
- যখন heap খালি না হয়:
  - (cost, x, y) := heapq.heappop(heap)
  - চার দিকের প্রতিবেশী (nx, ny) এর জন্য:
    - যদি is_valid(nx, ny) এবং matrix[nx][ny] + cost < dists[nx][ny], তবে আপডেট করুন এবং হিপে যোগ করুন
- dists ফেরত দিন
মূল পদ্ধতিতে:
- res := inf
- a := min_cost(row, col), b := min_cost(erow0, ecol0), c := min_cost(erow1, ecol1)
- সকল সেল (i, j) এর জন্য res = min(res, a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j])
- res ফেরত দিন

উদাহরণ

import heapq, math

class Solution:
    def solve(self, matrix, row, col, erow0, ecol0, erow1, ecol1):
        def is_valid(x, y):
            return x >= 0 and y >= 0 and x < len(matrix) and y < len(matrix[0])
        def min_cost(sx, sy):
            heap = [(matrix[sx][sy], sx, sy)]
            dists = [[math.inf] * len(matrix[0]) for _ in range(len(matrix))]
            dists[sx][sy] = matrix[sx][sy]
            while heap:
                cost, x, y = heapq.heappop(heap)
                for nx, ny in [(x, y-1), (x+1, y), (x-1, y), (x, y+1)]:
                    if is_valid(nx, ny) and matrix[nx][ny] + cost < dists[nx][ny]:
                        edge = matrix[nx][ny]
                        dists[nx][ny] = edge + cost
                        heapq.heappush(heap, (edge + cost, nx, ny))
            return dists
        res = math.inf
        a, b, c = min_cost(row, col), min_cost(erow0, ecol0), min_cost(erow1, ecol1)
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                res = min(res, a[i][j] + b[i][j] + c[i][j] - 2 * matrix[i][j])
        return res

ob = Solution()
matrix = [
    [1, 1, 1, 1, 1],
    [1, 10, 10, 10, 10],
    [1, 1, 1, 10, 10]
]
row = 0; col = 0; erow0 = 0; ecol0 = 3; erow1 = 2; ecol1 = 2
print(ob.solve(matrix, row, col, erow0, ecol0, erow1, ecol1))

ইনপুট

[[1, 1, 1, 1, 1], [1, 10, 10, 10, 10], [1, 1, 1, 10, 10]], 0, 0, 0, 3, 2, 2