পাইথনে মিনিমাম এফোর্ট পাথ বের করার প্রোগ্রাম

মান লিজিয়ে একটি m x n ২D ম্যাট্রিক্স আছে height। heights[i][j] হল সেল (i,j)-এর উঁচু। আমরা (0,0) থেকে শুরু করে বটম-রাইট (m-1,n-1)-এ যেতে চাই। আপ, ডাউন, লেফ্ট, রাইট যেতে পারি এবং ন্যূনতম এফোর্ট वाले পথ খুঁজতে চাই। এখানে পথের এফোর্ট হল পথের দুটি পরপর সেলের উঁচুর পার্থক্যের অ্যাবসোলিউট ভ্যালুর সর্বোচ্চ মান। ন্যূনতম এফোর্ট বের করতে হবে।

যেমন, ইনপুট হলে [[2,3,4],[4,9,5],[6,4,6]], তবে আউটপুট হবে 1 কারণ পথ [2,3,4,5,6]-এর সর্বোচ্চ অ্যাবসোলিউট ডিফারেন্স ১।

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

• r := len(heights), c := len(heights[0])

• queue := [(0,0,0)] (min-heap)

• queue খালি না থাকা পর্যন্ত:

  • cur := heappop(queue)

  • c_eff, x, y := cur

  • যদি x==r-1 and y==c-1 হয়, তবে c_eff রিটার্ন করুন।

  • যদি heights[x][y] == "" হয়, তবে কন্টিনিউ করুন।

  • প্রতিটি (dx,dy) in [(1,0),(-1,0),(0,1),(0,-1)] এর জন্য:

    • newx, newy := x+dx, y+dy

    • যদি ভ্যালিড এবং ভিজিটেড নয়, তবে:

      • eff := max(c_eff, abs(heights[newx][newy] - heights[x][y]))

      • heappush(queue, (eff, newx, newy))

  • heights[x][y] := "" (ভিজিটেড মার্ক)।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

import heapq
def solve(heights):
    r, c = len(heights), len(heights[0])
    queue = [(0, 0, 0)]
    while queue:
        cur = heapq.heappop(queue)
        c_eff, x, y = cur
        if x == r-1 and y == c-1:
            return c_eff
        if heights[x][y] == "":
            continue
        for dx, dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            newx, newy = x+dx, y+dy
            if 0 <= newx < r and 0 <= newy < c and heights[newx][newy] != "":
                eff = max(c_eff, abs(heights[newx][newy] - heights[x][y]))
                heapq.heappush(queue, (eff, newx, newy))
        heights[x][y] = ""
    return -1

matrix = [[2,3,4],[4,9,5],[6,4,6]]
print(solve(matrix))

ইনপুট

[[2,3,4],[4,9,5],[6,4,6]]

আউটপুট

1