POJ 2110 Mountain Walking：枚舉高度差 + BFS 判連通性

題目大意

N×N (≤100) 網格，每格有高度。從左上走到右下，只能上下左右移動。路徑上**最高點與最低點之差**最小化。

解題思路：雙重枚舉 + BFS

枚舉 `minH` 和 `maxH`，判斷是否存在路徑使所有經過格子高度 ∈ [minH, maxH]。
優化：枚舉 `diff = maxH - minH`，再枚舉 `minH`（或 `maxH`），`maxH = minH + diff`。
對固定區間，BFS 判連通性。

算法流程

1. 收集所有不同高度，排序去重 → `vals[]`
2. 二分答案 `diff`（或雙指針滑動窗口）
3. 對固定 `diff`，滑動窗口枚舉 `minH = vals[i]`，`maxH = minH + diff`
4. BFS 檢查 (0,0) 到 (N-1,N-1) 在高度區間內是否連通

代碼框架

int h[105][105];
bool vis[105][105];
int N;
vector vals;

bool bfs(int minH, int maxH) {
    if (h[0][0] < minH || h[0][0] > maxH) return false;
    memset(vis, 0, sizeof(vis));
    queue> q;
    q.push({0,0}); vis[0][0] = true;
    int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
    while (!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        if (x == N-1 && y == N-1) return true;
        for (int d = 0; d < 4; ++d) {
            int nx = x+dx[d], ny = y+dy[d];
            if (nx<0||nx>=N||ny<0||ny>=N||vis[nx][ny]) continue;
            if (h[nx][ny] < minH || h[nx][ny] > maxH) continue;
            vis[nx][ny] = true;
            q.push({nx,ny});
        }
    }
    return false;
}

bool check(int diff) {
    for (int minH : vals) {
        int maxH = minH + diff;
        if (maxH > vals.back()) break;
        if (bfs(minH, maxH)) return true;
    }
    return false;
}

int main() {
    cin >> N;
    vals.reserve(N*N);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j) {
            cin >> h[i][j];
            vals.push_back(h[i][j]);
        }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    
    int lo = 0, hi = vals.back() - vals.front(), ans = hi;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    cout << ans << '\n';
}

複雜度分析

• 高度去重：≤ 10⁴
• 二分：log(10⁴) ≈ 14 次
• 每次 check：滑動窗口 O(U) 次 BFS，U = 不同高度數 ≤ 10⁴
• BFS：O(N²) = 10⁴
• 總體：O(U × N² × log U) ≈ 10⁴ × 10⁴ × 14 = 1.4×10⁹ **過大！**

關鍵優化：雙指針滑動窗口替代二分+內層循環

由於 `minH` 和 `maxH` 都從 `vals` 取值，可用雙指針 `i,j` 維持窗口：

int ans = INF;
for (int i = 0, j = 0; i < vals.size(); ++i) {
    while (j < vals.size() && !bfs(vals[i], vals[j])) ++j;
    if (j == vals.size()) break;
    ans = min(ans, vals[j] - vals[i]);
}

複雜度降為 O(U × N²) = 10⁸，配合 BFS 早期剪枝可通過。

更優解法：Dijkstra 類最短路變體

狀態 = (x,y, minH, maxH) 太大。實際可用「最小化最大高度差」的優先隊列搜索，但雙指針+BFS 已足夠。