Path With Maximum Minimum Value: Tìm Đường Đi Max-Min Trên Ma Trận (Dijkstra/Heap)

Đề bài: Ma trận R x C số nguyên. Tìm đường từ (0,0) đến (R-1,C-1) (đi 4 hướng) sao cho giá trị nhỏ nhất trên đường đi là lớn nhất có thể. Trả về giá trị min đó.

Ví dụ: Ma trận 3x3, đường đi màu cam → min value = 4.

Ý tưởng: Maximum Capacity Path / Widest Path (Dijkstra biến thể)

Dùng Max-Heap (priority queue) ưu tiên ô có giá trị lớn nhất. Tại mỗi bước, lấy ô có value lớn nhất chưa visited, cập nhật neighbor. Giá trị path đến neighbor = min(current_path_min, neighbor_value).

Tương tự Dijkstra nhưng thay "min distance" bằng "max of min values".

Code Python

import heapq

class Solution:
    def maximumMinimumPath(self, A: list[list[int]]) -> int:
        R, C = len(A), len(A[0])
        # Max-heap: store (-value, r, c) vì heapq là min-heap
        heap = [(-A[0][0], 0, 0)]
        visited = [[False]*C for _ in range(R)]
        visited[0][0] = True
        
        # Upper bound: min of start and end
        ans = min(A[0][0], A[-1][-1])
        
        while heap:
            neg_val, r, c = heapq.heappop(heap)
            val = -neg_val
            ans = min(ans, val)
            
            if r == R-1 and c == C-1:
                break
            
            for dr, dc in [(-1,0),(1,0),(0,1),(0,-1)]:
                nr, nc = r+dr, c+dc
                if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc]:
                    visited[nr][nc] = True
                    heapq.heappush(heap, (-A[nr][nc], nr, nc))
        
        return ans

# Test
ob = Solution()
grid = [[5,4,5],[1,2,6],[7,4,6]]
print(ob.maximumMinimumPath(grid))  # 4

Giải thích test case

Path: (0,0)=5 → (0,1)=4 → (0,2)=5 → (1,2)=6 → (2,2)=6. Min = 4. Không có path nào min > 4.

Phân tích

• Time: O(RC log(RC)) heap operations.
• Space: O(RC) visited + heap.
• Greedy: luôn mở rộng từ ô "hứa hẹn" nhất (giá trị cao).

Biến thể: Binary Search + BFS/DFS

Binary search answer mid, check có path nào toàn giá trị ≥ mid không (BFS/DFS). O(log(max_val) * RC).

Kết luận

Max-Min path = Widest Path problem. Max-heap Dijkstra variant là giải pháp trực quan, hiệu quả. Pattern: "maximize the minimum" → priority queue descending.