NYOJ 306 走迷宮 (DFS + 二分答案)

問題描述

N×N 迷宮 (2≤N≤100)，每格有難度值 (0~120)。從左上角 (1,1) 走到右下角 (N,N)，可上下左右移動。尋找一條路徑，使路徑上最大難度與最小難度之差最小。輸出這個最小差值。多組測試，EOF 結束。

解題思路：二分答案 + DFS 判定

1. 難度差範圍 [0, maxVal-minVal]。二分中間值 mid。
2. 判定是否存在路徑使所有經過格子難度在某長度為 mid 的區間 [L, L+mid] 內。枚舉 L 從 minVal 到 maxVal-mid，若起點終點難度不在區間內則跳過，否則 DFS 搜索是否可達終點。
3. 若存在合法路徑，縮小上界；否則增大下界。

關鍵代碼片段

int n, minV, maxV, flag;
int vis[120][120], mp[120][120];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};

void dfs(int x, int y, int L, int R) {
    if (flag) return;
    if (x == n && y == n) { flag = 1; return; }
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (mp[nx][ny] >= L && mp[nx][ny] <= R && !vis[nx][ny]) {
            vis[nx][ny] = 1;
            dfs(nx, ny, L, R);
        }
    }
}

bool check(int diff) {
    for (int L = minV; L <= maxV - diff; ++L) {
        flag = 0;
        if (mp[1][1] < L || mp[1][1] > L + diff) continue;
        if (mp[n][n] < L || mp[n][n] > L + diff) continue;
        memset(vis, 0, sizeof(vis));
        vis[1][1] = 1;
        dfs(1, 1, L, L + diff);
        if (flag) return true;
    }
    return false;
}

int solve() {
    int l = 0, r = maxV - minV;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

複雜度分析

二分 O(log 120) ≈ 7 次，每次枚舉 L 最多 120 次，DFS O(N²)。總複雜度 O(log V · V · N²) ≈ 7×120×10⁴ = 8.4×10⁶，極快。

樣例

輸入：5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1
輸出：2