Chương trình tìm đường đi nỗ lực tối thiểu trong ma trận trong Python

Ma trận heights m x n. Từ (0,0) đến (m-1,n-1), di chuyển 4 hướng. Nỗ lực đường đi = max |chênh lệch cao độ| giữa 2 ô liên tiếp. Tìm nỗ lực tối thiểu.

Ví dụ: [[2,3,4],[4,9,5],[6,4,6]] → 1. Đường: 2→3→4→5→6 (chênh lệch max = 1).

Giải thuật (Dijkstra / Priority Queue)

1. Priority queue lưu (effort, x, y), ưu tiên effort nhỏ.
2. Pop trạng thái effort nhỏ nhất. Nếu đến đích → trả về effort.
3. Nếu ô đã thăm (đánh dấu bằng chuỗi rỗng) → bỏ qua.
4. Mở rộng 4 hướng: tính eff = max(curr_eff, abs(heights[nx][ny] - heights[x][y])), push vào queue.
5. Đánh dấu ô hiện tại đã thăm.

Ví dụ minh họa

import heapq

def solve(heights):
    r, c = len(heights), len(heights[0])
    queue = [(0, 0, 0)]
    while queue:
        c_eff, x, y = heapq.heappop(queue)
        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]]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < r and 0 <= ny < c and heights[nx][ny] != "":
                eff = max(c_eff, abs(heights[nx][ny] - heights[x][y]))
                heapq.heappush(queue, (eff, nx, ny))
        heights[x][y] = ""
    return -1

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

Đầu vào

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

Đầu ra

1