AOJ 0033 Ball - 10 顆球雙棧排序 DFS 回溯求解

問題描述

有 10 個球（編號 1-10）從上方依次落下，每球可選擇進入左邊或右邊軌道。所有球落下後，若左右兩軌道球的編號均為從小到大順序，輸出 YES，否則 NO。

核心觀察

• 每個軌道內部必須保持遞增序列
• 新球只能放在比它大的球之後（即軌道頂端球 < 新球）
• 這是一個典型的雙棧排序問題，用 DFS 回溯搜尋所有可行分配方案

DFS 回溯解法

#include 
#include 
using namespace std;

bool flag = true;

void solve(queue left, queue right, queue all) {
    if (all.empty()) return;  // 所有球已分配完畢
    
    int ball = all.front();
    
    // 嘗試放入左軌道
    if (left.empty() || ball > left.back()) {
        left.push(ball);
        all.pop();
        solve(left, right, all);
        if (!flag) return;  // 已找到解或無解，剪枝
        all.push(ball);     // 回溯
        left.pop();
    }
    
    // 嘗試放入右軌道
    if (right.empty() || ball > right.back()) {
        right.push(ball);
        all.pop();
        solve(left, right, all);
        if (!flag) return;
        all.push(ball);
        right.pop();
    }
    
    // 兩條軌道都放不下
    flag = false;
}

int main() {
    int n; 
    scanf("%d", &n);
    while (n--) {
        queue all;
        for (int i = 0; i < 10; ++i) {
            int x; scanf("%d", &x);
            all.push(x);
        }
        flag = true;
        queue left, right;
        solve(left, right, all);
        printf("%s\n", flag ? "YES" : "NO");
    }
    return 0;
}

迭代版 DFS（使用棧模擬）

#include 
#include 
using namespace std;

int main() {
    int n; cin >> n;
    while (n--) {
        int a[10];
        for (int i = 0; i < 10; ++i) cin >> a[i];
        
        stack left, right;
        left.push(0); right.push(0);  // 哨兵
        bool used[11] = {};           // 記錄每球放左/右
        int idx = 0;
        bool ok = true;
        
        while (idx >= 0) {
            int ball = a[idx];
            bool placed = false;
            
            // 嘗試放左
            if (left.top() < ball && !used[ball]) {
                left.push(ball);
                used[ball] = true;  // true=左
                ++idx;
                placed = true;
            }
            // 嘗試放右
            else if (right.top() < ball && !used[ball]) {
                right.push(ball);
                used[ball] = false; // false=右
                ++idx;
                placed = true;
            }
            
            if (!placed) {  // 回溯
                if (idx == 0) { ok = false; break; }
                --idx;
                int prev = a[idx];
                if (used[prev]) left.pop();
                else right.pop();
                used[prev] = false;  // 重置，下次嘗試另一側
            }
            
            if (idx == 10) break;  // 全部放置成功
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
}

關鍵點總結

1. 狀態表示：兩個棧/隊列分別模擬左右軌道，只需記錄頂端元素
2. 可行性條件：新球 > 軌道頂端球（保證遞增）
3. 搜尋策略：DFS 回溯嘗試所有分配組合，找到一組可行解即可
4. 剪枝：一旦發現無法放置且無回溯路徑，直接返回 NO