สมมติว่าเรามีเมทริกซ์ M โดยที่ M[r][c] แทนความสูงของเซลล์นั้น หากตอนนี้เราอยู่ที่มุมซ้ายบนและต้องการไปที่มุมล่างขวา เราสามารถย้ายไปยังเซลล์ที่อยู่ติดกัน (ขึ้น ลง ซ้าย ขวา) ได้ก็ต่อเมื่อความสูงของเซลล์ที่อยู่ติดกันนั้นน้อยกว่าหรือเท่ากับความสูงของเซลล์ปัจจุบัน เราสามารถเพิ่มความสูงของเซลล์จำนวนเท่าใดก็ได้ก่อนที่เราจะย้าย ดังนั้นเราต้องค้นหาความสูงรวมขั้นต่ำที่ต้องเพิ่มเพื่อไปที่เซลล์ด้านขวาล่าง
ดังนั้นหากอินพุตเป็นแบบ
| 2 | 4 | 5 |
| 8 | 6 | 1 |
จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากเราสามารถใช้เส้นทางต่อไปนี้ [2, 4, 5, 1] และเปลี่ยนความสูงเป็นการกำหนดค่านี้ -
| 5 | 5 | 5 |
| 8 | 6 | 1 |
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
INF :=อินฟินิตี้
-
R, C :=หมายเลขแถวของเมทริกซ์, หมายเลขคอลัมน์ของเมทริกซ์
-
pq :=สร้างลำดับความสำคัญของคิวโดยใช้ฮีปและแทรก [0, R-1, C-1, M[-1, -1]] ลงในนั้น
-
dist :=แผนที่
-
dist[R-1, C-1, A[-1, -1]] :=0
-
ในขณะที่ pq ไม่ว่างเปล่าให้ทำ
-
ลบหนึ่งองค์ประกอบจาก pq และเก็บไว้ใน d, r, c, h
-
ถ้า dist[r, c, h]
-
ไปอ่านตอนต่อไป
-
-
ถ้า r และ c เป็นทั้ง 0 แล้ว
-
กลับ d
-
-
สำหรับแต่ละคู่ (nr, nc) ใน [[r+1, c], [r, c+1], [r-1, c], [r, c-1]] ทำ
-
ถ้า 0 <=nr
-
ถ้า d2
-
dist[nr, nc, h2] :=d2
-
แทรก [d2, 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]]
ผลลัพธ์
4
