您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

Topcoder SRM 646 Div1 600：BFS + 剪枝求最大達達標距離

編輯：關於C++

Topcoder SRM 646 Div1 600「TheGridDivOne」：在無限網格中，從 (0,0) 出發，最多 k 步，某些格子有障礙物。每步可上下左右移動，但向右移動無步數限制（可一次移多格直到障礙或邊界）。求最大達到的 x 座標。本文解析 BFS 狀態空間搜索 + 優先向右貪心 + 剪枝優化。

問題建模

狀態：(x, y, steps)，當前位置與已用步數。
移動：
上/下/左：單步，消耗 1 步數。
右：可連續移動至障礙前/邊界，消耗移動格數步數。
障礙：給定 x[], y[] 數組，最多 47 個。
目標：最大化 x。

關鍵觀察

障礙稀疏：只有 ≤47 個障礙，大部分空間空曠。
向右貪心：無障礙時應盡量向右走，因為目標是最大化 x。
有效區域有限：偏離障礙太遠無意義，可限制搜索範圍（如 |x|,|y| ≤ 50）。

BFS + 剪枝策略

隊列存 {x, y, k}。
map<pair<int,int>, int> dist 記錄到達 (x,y) 的最小步數。
若新到達步數 ≥ 已記錄步數，剪枝。
關鍵剪枝：x + (K - k) <= bestX 則無法超越當前最佳，剪枝（因最多每步右移 1）。
優先處理向右移動：計算右側最近障礙/邊界，直接跳躍。

核心代碼邏輯（C++）

struct State { int x, y, k; };

int find(vector<int> xs, vector<int> ys, int K) {
    int n = xs.size();
    queue<State> q;
    map<pair<int,int>, int> best;
    q.push({0, 0, 0});
    best[{0,0}] = 0;
    int ans = 0;

    while (!q.empty()) {
        State cur = q.front(); q.pop();
        if (cur.k > K) continue;
        ans = max(ans, cur.x);

        // 剪枝：即使全往右走也超不過 ans
        if (cur.x + (K - cur.k) <= ans) continue;

        // 找四方向最近障礙
        int U = INF, D = -INF, L = -INF, R = INF;
        for (int i = 0; i < n; ++i) {
            if (xs[i] == cur.x) {
                if (ys[i] > cur.y) U = min(U, ys[i]);
                if (ys[i] < cur.y) D = max(D, ys[i]);
            }
            if (ys[i] == cur.y) {
                if (xs[i] > cur.x) R = min(R, xs[i]);
                if (xs[i] < cur.x) L = max(L, xs[i]);
            }
        }

        // 1. 向右跳躍（貪心優先）
        int nx = min(cur.x + K - cur.k, R - 1);
        if (nx > cur.x) {
            State ns = {nx, cur.y, cur.k + nx - cur.x};
            if (!best.count({nx, cur.y}) || best[{nx, cur.y}] > ns.k) {
                best[{nx, cur.y}] = ns.k;
                q.push(ns);
            }
        }

        // 2. 向左/上/下：僅嘗試 1 步（因遠離障礙無意義）
        for (int dx = -1; dx <= 1; ++dx) for (int dy = -1; dy <= 1; ++dy) {
            if (dx == 0 && dy == 0) continue;
            if (dx != 0 && dy != 0) continue; // 僅四連通
            int nx = cur.x + dx, ny = cur.y + dy, nk = cur.k + 1;
            if (nk > K) continue;
            // 邊界檢查：不超過障礙
            if (dx == 1 && nx >= R) continue;
            if (dx == -1 && nx <= L) continue;
            if (dy == 1 && ny >= U) continue;
            if (dy == -1 && ny <= D) continue;
            if (!best.count({nx, ny}) || best[{nx, ny}] > nk) {
                best[{nx, ny}] = nk;
                q.push({nx, ny, nk});
            }
        }
    }
    return ans;
}