สมมติว่าเรามีเมทริกซ์ A ของจำนวนเต็มที่มีแถว R และคอลัมน์ C เราต้องหาคะแนนสูงสุดของเส้นทางที่เริ่มต้นจาก [0,0] และสิ้นสุดที่ [R-1,C-1] ที่นี่เทคนิคการให้คะแนนจะเป็นค่าต่ำสุดในเส้นทางนั้น ตัวอย่างเช่น ค่าของเส้นทาง 8 → 4 → 5 → 9 คือ 4 เส้นทางจะย้ายจำนวนครั้งจากเซลล์ที่เข้าชมหนึ่งไปยังเซลล์ที่ไม่ได้เยี่ยมชมที่อยู่ใกล้เคียงในหนึ่งจาก 4 ทิศทางที่สำคัญ (เหนือ ตะวันออก ตะวันตก ใต้) .
ตัวอย่างเช่น ถ้าเส้นกริดเป็นแบบ −
| 5 | 4 | 5 |
| 1 | 2 | 6 |
| 7 | 4 | 6 |
เซลล์สีส้มจะเป็นเส้นทาง ผลลัพธ์คือ 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- r :=จำนวนแถว และ c :=จำนวนคอลัมน์
- ans :=ขั้นต่ำของ A[0, 0] และ A[r – 1, c – 1]
- สร้างเมทริกซ์หนึ่งเมทริกซ์ที่เรียกว่า visit ของลำดับเหมือนกับ A และเติมด้วย FALSE
- h :=รายการที่เราเก็บ tuple (-A[0, 0], 0, 0)
- สร้างฮีปจาก h
- ในขณะที่ h ไม่ว่างเปล่า
- v, x, y :=ลบ h ออกจาก heap และเก็บสามค่า
- ถ้า x =r – 1 และ y :=c – 1 แล้วออกจากลูป
- ans :=นาทีของ ans, A[x, y]
- เข้าชมแล้ว[x, y] :=true
- สำหรับ dy, dx ในรายการ [(-1, 0), (1, 0), (0, 1), (0, -1)], ทำ
- a :=x + dx และ b :=y + dy
- ถ้า a อยู่ในช่วง 0 ถึง r – 1 และ b อยู่ในช่วง 0 ถึง c – 1 และเข้าชม[a, b] เป็นเท็จ
- แทรก (-A[a, b], a, b) ลงในฮีปด้วย h
- คืนสินค้า
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
import heapq
class Solution(object):
def maximumMinimumPath(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
r,c = len(A),len(A[0])
ans = min(A[0][0],A[-1][-1])
visited = [[False for i in range(c)] for j in range(r)]
h = [(-A[0][0],0,0)]
heapq.heapify(h)
while h:
# print(h)
v,x,y = heapq.heappop(h)
if x== r-1 and y == c-1:
break
ans = min(ans,A[x][y])
visited[x][y]= True
for dx,dy in {(-1,0),(1,0),(0,1),(0,-1)}:
a,b = x+dx,y+dy
if a>=0 and a<r and b>=0 and b<c and not visited[a][b]:
heapq.heappush(h,(-A[a][b],a,b))
return ans อินพุต
[[5,4,5],[1,2,6],[7,4,6]]
ผลลัพธ์
4
