Path With Maximum Minimum Value: หาเส้นทางที่ค่า Min สูงสุด (Maximin Path)

โจทย์

กำหนด Matrix A (R×C) หา path จาก [0,0] ไป [R-1,C-1] (4 ทิศทาง) ที่ Maximum Minimum Value (ค่า minimum บน path สูงสุดเท่าที่จะเป็น)

ตัวอย่าง:

5 4 5
1 2 6
7 4 6

อัลกอริทึม: Modified Dijkstra / BFS with Max-Heap (Priority Queue)

State: (min_value_on_path, row, col) ใช้ Max-Heap (priority = -min_value) เพื่อ explore path ที่มี min สูงสุดก่อน

• เริ่ม: (-A[0][0], 0, 0)
• Pop state ที่มี min สูงสุด (priority queue)
• ถ้าถึง destination → คืนค่า min_value นั้น (guaranteed optimal)
• Expand เพื่อนบ้าน 4 ทิศทาง: new_min = min(current_min, A[nr][nc])
• Visited set กันซ้ำ

การติดตั้ง (Python Implementation)

import heapq

class Solution:
    def maximumMinimumPath(self, A: list[list[int]]) -> int:
        R, C = len(A), len(A[0])
        # Max heap: (-min_value, r, c)
        heap = [(-A[0][0], 0, 0)]
        visited = [[False] * C for _ in range(R)]
        visited[0][0] = True
        
        # Answer is at least min(start, end)
        ans = min(A[0][0], A[-1][-1])
        
        while heap:
            neg_min_val, r, c = heapq.heappop(heap)
            curr_min = -neg_min_val
            
            # Update answer (path to here has min = curr_min)
            ans = min(ans, curr_min)
            
            if r == R-1 and c == C-1:
                return ans  # Reached destination with max possible min
            
            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
                    new_min = min(curr_min, A[nr][nc])
                    heapq.heappush(heap, (-new_min, nr, nc))
        
        return ans

# ทดสอบ
ob = Solution()
grid = [[5,4,5],[1,2,6],[7,4,6]]
print(ob.maximumMinimumPath(grid))  # 4

# ทดสอบเพิ่ม
print(ob.maximumMinimumPath([[2,2,1],[2,2,2]]))  # 2

Output

4
2

ทำไม Dijkstra/Max-Heap ถูกต้อง?

• เราต้องการ maximize minimum value → ค้นหา path ที่ "bottleneck" สูงสุด
• Max-heap รับประกันว่าเรา explore path ที่มี potential สูงสุดก่อน
• เมื่อถึง destination ครั้งแรก → นัคคือคำตอบ (เพราะ path อื่นจะมี min ≤ นี้)
• คล้ายกับ "Maximum Capacity Path" หรือ "Widest Path Problem"

Alternative: Binary Search + BFS/DFS

Binary search คำตอบ mid, check ถ้ามี path ทั้งหมด ≥ mid (BFS/DFS) O(RC log MaxVal)

Complexity

• Time: O(RC log(RC)) - Heap operations
• Space: O(RC) - Visited + Heap

สรุป

Path With Maximum Minimum Value = Widest Path Problem ใช้ Max-Heap Dijkstra variant หา path ที่ bottleneck สูงสุด Optimal และเข้าใจง่าย

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ