藍橋杯算法訓練 Lift and Throw：三角色移動舉扔達到最遠位置完整 C++ 解法

題目簡述

三角色（Laharl, Etna, Flonne）初始位置各異，各有移動範圍、投擲範圍。每角色可移動一次、舉起一次、投擲一次。可疊人（舉起已舉人者），最底者可投擲整堆。求任一角色能到達的最大座標。

核心思路：9 動作全排列 + 狀態回溯

• 3 角色 × 3 動作 = 9 個原子動作，生成所有排列（9! = 362,880 種），每種模擬執行並記錄最遠位置。
• 狀態包含：位置、是否被舉、是否舉人、移動/投擲是否已用、移動/投擲範圍。
• 剪枝：投擲後被投者仍可移動，直接計算理論最遠值更新答案，避免繼續遞歸。

關鍵代碼片段（完整代碼見原文）

struct Person {
    int pos, mvmax, thrmax;
    bool held, holding, mvUsed, thrUsed;
};

int maxPos = 0;
int occupied[50]; // 位置佔用標記

void dfs(int step, vector& perm) {
    if (step == 9) return;
    int p = perm[step] / 3;      // 角色 0~2
    int act = perm[step] % 3;    // 0移動 1舉起 2投擲
    Person& me = people[p];

    if (act == 0) { // 移動
        if (me.held || me.holding) return;
        for (int d = -me.mvmax; d <= me.mvmax; d++) if (d != 0) {
            int np = me.pos + d;
            if (np > 0 && !occupied[np]) {
                occupied[me.pos] = 0; occupied[np] = p+1;
                me.pos = np; me.mvUsed = true;
                maxPos = max(maxPos, np + me.mvmax); // 剪枝：還能再移動最遠
                dfs(step+1, perm);
                me.mvUsed = false; me.pos = me.pos - d;
                occupied[np] = 0; occupied[me.pos] = p+1;
            }
        }
    } else if (act == 1) { // 舉起
        if (me.held) return;
        for (int dir : {-1, 1}) {
            int targetPos = me.pos + dir;
            if (targetPos > 0 && occupied[targetPos]) {
                int q = occupied[targetPos] - 1;
                if (!people[q].held) {
                    me.holding = true; people[q].held = true;
                    occupied[targetPos] = 0;
                    dfs(step+1, perm);
                    me.holding = false; people[q].held = false;
                    occupied[targetPos] = q+1;
                }
            }
        }
    } else { // 投擲
        if (!me.holding || me.held) return;
        int q = -1;
        for (int i=0;i<3;i++) if (people[i].held && people[i].holding==false) { q=i; break; } // 簡化：假設只舉一人
        if (q==-1) return;
        for (int d = -me.thrmax; d <= me.thrmax; d++) if (d != 0) {
            int np = me.pos + d;
            if (np > 0 && !occupied[np]) {
                people[q].pos = np; people[q].held = false;
                occupied[np] = q+1; me.thrUsed = true;
                maxPos = max(maxPos, np + people[q].mvmax); // 被投者落地後仍可移動
                dfs(step+1, perm);
                me.thrUsed = false; people[q].held = true;
                occupied[np] = 0;
            }
        }
    }
}

樣例驗證

輸入：
9 3 3
4 3 1
2 3 3
輸出：15

符合官方樣例說明路徑。

複雜度與優化

• 9! ≈ 36 萬排列，每排列模擬常數操作，總運算 < 10^7，遠小於 1 秒限制。
• 可加入備忘錄（狀態壓縮 DP）進一步剪枝，但非必要。