โปรแกรมหาเส้นทางที่ความพยายามน้อยที่สุดใน Python

ปัญหา

เมทริกซ์ height m x n เริ่ม (0,0) ไป (m-1,n-1) เดิน 4 ทิศทาง "ความพยายาม" = ความต่างสัมบูรณ์สูงสุดระหว่างเซลล์ติดกันในเส้นทาง หาเส้นทางที่ความพยายามน้อยที่สุด

ตัวอย่าง

[[2,3,4],[4,9,5],[6,4,6]] → ผลลัพธ์ 1 (เส้นทาง 2→3→4→5→6 ความต่างสูงสุด = 1)

ขั้นตอนการแก้ปัญหา

1. r, c := rows, cols
2. queue := [(0,0,0)] (min-heap: effort, x, y)
3. بينما queue:
   • c_eff, x, y := heappop(queue)
   • ถ้า x==r-1 and y==c-1: คืน c_eff
   • ถ้า heights[x][y] == "": continue (เยี่ยมแล้ว)
   • สำหรับ dx,dy ใน 4 ทิศทาง:
     • newx, newy := x+dx, y+dy
     • ถ้าในขอบเขตและยังไม่เยี่ยม: eff := max(c_eff, abs(heights[newx][newy] - heights[x][y])), push (eff, newx, newy)
   • heights[x][y] := "" (mark visited)

การนำไปใช้งาน (Python)

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]]:
            newx = x + dx
            newy = 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