1631. Path With Minimum Effort
解題說明
Path With Minimum Effort
題目描述：給定一個 rows × columns 的整數矩陣 heights，代表地形高度。從左上角 (0, 0) 走到右下角 (rows-1, cols-1)，每步只能上下左右移動。一條路徑的 effort 定義為路徑上相鄰格子高度差絕對值的最大值。求所有可能路徑中，effort 最小的路徑之 effort 值。
解題思路：
本題有三種主要解法，最直觀且高效的是 Dijkstra 變形，也可以用 Kruskal Union-Find 解決。
方法一：Dijkstra 變形（推薦）
定義 dist[r][c] 為「從起點到達 (r,c) 所需的最小 effort」。初始 dist[0][0] = 0，其餘為無限大。
用最小堆（priority queue）貪心擴展：每次取出當前 effort 最小的格子 (r, c, eff)，嘗試向四個方向擴展：newEff = max(eff, |heights[nr][nc] - heights[r][c]|)。若 newEff < dist[nr][nc]，更新並加入堆。到達右下角時立即回傳。
方法二：Kruskal Union-Find
將所有相鄰格子對視為邊，邊權為高度差絕對值。按邊權升序排序（即 Kruskal 算法）。依序加邊並 union，直到左上角 (0,0) 和右下角 (rows-1, cols-1) 在同一連通分量中，當前邊的邊權即為答案。
原理：最小的使起終點連通的邊，就是瓶頸最小路徑（minimax path）上的最大邊——這正是 Kruskal MST 的瓶頸最短路定理。
方法三：二分搜尋 + BFS/DFS
二分搜尋答案 mid，用 BFS/DFS 驗證是否存在 effort ≤ mid 的路徑。時間 O(m·n·log(maxHeight))。
C++ 解法
複雜度分析
方法一 Dijkstra：
- 時間複雜度：O(m·n·log(m·n)) — 每個格子最多入堆一次，堆操作 O(log(m·n))，共 m·n 個格子。
- 空間複雜度：O(m·n) —
dist陣列與 priority queue 各 O(m·n)。
方法二 Kruskal Union-Find：
- 時間複雜度：O(m·n·log(m·n)) — 建邊 O(m·n)，排序 O(m·n·log(m·n))，Union-Find O(m·n·α(m·n))，總體由排序主導。
- 空間複雜度：O(m·n) — 邊列表 O(m·n)，Union-Find 陣列 O(m·n)。
方法三 二分搜尋 + BFS：
- 時間複雜度：O(m·n·log(maxH)) — 二分 O(log(maxH))，每次 BFS O(m·n)。
- 空間複雜度：O(m·n)。
虛擬碼
// Method 1: Dijkstra
1. Initialize dist[r][c] = INF for all cells; dist[0][0] = 0
2. Push (effort=0, r=0, c=0) into min-heap
3. While heap not empty:
a. Pop (eff, r, c) with minimum effort
b. If (r,c) == destination: return eff
c. If eff > dist[r][c]: skip (stale entry)
d. For each neighbor (nr, nc):
- newEff = max(eff, |heights[nr][nc] - heights[r][c]|)
- If newEff < dist[nr][nc]:
dist[nr][nc] = newEff; push (newEff, nr, nc)
// Method 2: Kruskal Union-Find
1. Build all edges (weight=|h1-h2|, nodeA, nodeB) for adjacent cells
2. Sort edges by weight ascending
3. Initialize Union-Find for all m*n nodes
4. For each edge (w, a, b) in sorted order:
unite(a, b)
If find(src) == find(dst): return w
5. Return 0其他解法
二分搜尋 + BFS/DFS O(m·n·log(maxH))：對答案 effort 二分搜尋，每次驗證「是否存在 effort ≤ mid 的路徑」只需 BFS/DFS（只走高度差 ≤ mid 的相鄰格）。優點是不需要 Dijkstra 或 Union-Find 的知識，只用基礎 BFS；缺點是需要對 maxH（最大高度差）做二分，常數略大，且比 Dijkstra 多一個 log 因子（雖然 log 2×10⁴ ≈ 15，實際差距不大）。
Bellman-Ford 變形 O((m·n)²)：傳統 Bellman-Ford 做 n-1 輪鬆弛，每輪掃描所有邊，可求瓶頸最短路。優點是不需要排序或堆；缺點是時間複雜度 O((m·n)²)，對 m·n=10⁴ 的網格共 10⁸ 次操作，會超時。僅作為理論比較。
Kruskal Union-Find（已在 solution_code 中提供）：利用「最小瓶頸路徑」等於 MST 上兩點路徑的性質，按邊權排序後依序 union，直到起終點連通為止。與 Dijkstra 時間複雜度相同，但思路更接近圖論中的 Kruskal MST。在實作上比 Dijkstra 略繁瑣（需建邊並排序），但更適合用來理解問題的圖論本質。
延伸思考
- 若允許斜向移動（八個方向），解法需要如何調整？複雜度是否改變？
- 本題的「最小 effort 路徑」等於「起終點在 MST 上路徑的最大邊權」（即最小瓶頸路徑定理）。請解釋這個等價性的數學原理。
- 若問題改為「最小化路徑上所有相鄰高度差之和」（而非最大值），Dijkstra 是否仍然適用？這是傳統最短路問題嗎？