Giả sử chúng ta có một ma trận A gồm các số nguyên với R hàng và C cột, chúng ta phải tìm điểm lớn nhất của một đường bắt đầu từ [0,0] và kết thúc tại [R-1, C-1]. Ở đây kỹ thuật tính điểm sẽ là giá trị nhỏ nhất trong đường dẫn đó. Ví dụ:giá trị của đường dẫn 8 → 4 → 5 → 9 là 4. Một đường dẫn di chuyển một số lần từ một ô được truy cập sang bất kỳ ô nào chưa được truy cập lân cận theo một trong 4 hướng chính (bắc, đông, tây, nam) .
Ví dụ:nếu lưới giống như -
| 5 | 4 | 5 |
| 1 | 2 | 6 |
| 7 | 4 | 6 |
Các ô màu cam sẽ là đường dẫn. Đầu ra là 4
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- r:=số hàng và c:=số cột
- ans:=tối thiểu A [0, 0] và A [r - 1, c - 1]
- tạo một ma trận được gọi là đã truy cập có thứ tự giống như A và điền vào điều này bằng FALSE
- h:=một danh sách, nơi chúng tôi lưu trữ một bộ giá trị (-A [0, 0], 0, 0)
- Tạo đống từ h
- trong khi h không trống
- v, x, y:=xóa h khỏi heap và lưu trữ ba giá trị
- nếu x =r - 1 và y:=c - 1, thì thoát khỏi vòng lặp
- ans:=min of ans, A [x, y]
- đã ghé thăm [x, y]:=true
- cho dy, dx trong danh sách [(-1, 0), (1, 0), (0, 1), (0, -1)], thực hiện
- a:=x + dx và b:=y + dy
- nếu a trong phạm vi 0 đến r - 1 và b trong phạm vi 0 đến c - 1 và đã thăm [a, b] là sai,
- chèn (-A [a, b], a, b) vào heap với h
- trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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 Đầu vào
[[5,4,5],[1,2,6],[7,4,6]]
Đầu ra
4