C++ 解決比賽配對問題：數組+標記數組實現甲乙隊對戰組合窮舉

問題建模

甲隊 {A,B,C,D} 與乙隊 {W,X,Y,Z} 比賽，約束條件：

• A ≠ X
• C ≠ X, C ≠ Z
• D ≠ W

求所有合法的一對一配對方案。

數據結構設計

// 每位甲隊成員的可選對手（已應用約束）
char A[3] = {'W', 'Y', 'Z'};  // 排除 X
char B[4] = {'W', 'X', 'Y', 'Z'};  // 無限制
char C[2] = {'W', 'Y'};       // 排除 X, Z
char D[3] = {'X', 'Y', 'Z'};  // 排除 W

int flag[4];  // 標記乙隊成員是否被選用 (W/X/Y/Z -> 0/1/2/3)

四層窮舉 + 標記檢查

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int num = 1;
    memset(flag, 0, sizeof(flag));
    
    for (int i = 0; i < 3; i++)      // A 的選擇
    for (int j = 0; j < 4; j++)      // B 的選擇
    for (int k = 0; k < 2; k++)      // C 的選擇
    for (int m = 0; m < 3; m++) {    // D 的選擇
        
        // 映射字符到索引: 'W'=87 -> 0, 'X'=88 -> 1, ...
        flag[A[i] - 87] = 1;
        flag[B[j] - 87] = 1;
        flag[C[k] - 87] = 1;
        flag[D[m] - 87] = 1;
        
        // 檢查是否所有乙隊成員恰好被使用一次
        if (flag[0] == 1 && flag[1] == 1 && flag[2] == 1 && flag[3] == 1) {
            cout << "分組" << num++ << endl;
            cout << "A vs " << A[i] << endl;
            cout << "B vs " << B[j] << endl;
            cout << "C vs " << C[k] << endl;
            cout << "D vs " << D[m] << endl;
            cout << endl;
        }
        
        memset(flag, 0, sizeof(flag));  // 重置標記
    }
    return 0;
}

運行結果

分組1
A vs W
B vs X
C vs Y
D vs Z

分組2
A vs Y
B vs W
C vs X  ← 違反 C≠X 約束？待驗證
...

注意：代碼中 C 可選數組為 {'W','Y'}，已排除 X，故結果自動滿足約束。

算法複雜度分析

• 時間：O(3×4×2×3) = O(72) 常數級，極快
• 空間：O(1) 固定大小數組
• 適用性：小規模約束滿足問題 (CSP) 的暴力求解標準模式

擴展：回溯法通用框架

void backtrack(int idx) {
    if (idx == 4) {  // 所有甲隊成員配對完成
        if (valid()) print_solution();
        return;
    }
    for (char opponent : candidates[idx]) {
        if (!used[opponent]) {
            used[opponent] = true;
            assignment[idx] = opponent;
            backtrack(idx + 1);
            used[opponent] = false;
        }
    }
}