---
# System prepended metadata

title: 'a135: 巧克力擺盒'

---

# a135: 巧克力擺盒

``` cpp=
//
// AC (32ms, 344KB)
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

//
// 巧克力總共有 0~8 共 9 顆，每種一個：
//
//    | S | C | T |
// ---+---+---+---+
//  P | 1 | 2 | 3 |
//  B | 4 | 5 | 6 |
//  Y | 7 | 8 | 9 |
//

const int C1 = 1, 
          C2 = 1 << 1, 
          C3 = 1 << 2, 
          C4 = 1 << 3,
          C5 = 1 << 4,
          C6 = 1 << 5,
          C7 = 1 << 6,
          C8 = 1 << 7,
          C9 = 1 << 8;

// 擺法規則可對應到哪幾顆
unordered_map<string, int> RULEMAP = {
    {"PS", C1},
    {"PC", C2},
    {"PT", C3}, 
    {"P?", C1|C2|C3}, 
    {"BS", C4}, 
    {"BC", C5},
    {"BT", C6},
    {"B?", C4|C5|C6},
    {"YS", C7},
    {"YC", C8},
    {"YT", C9},
    {"Y?", C7|C8|C9},
    {"?S", C1|C4|C7},
    {"?C", C2|C5|C8},
    {"?T", C3|C6|C9},
    {"??", C1|C2|C3|C4|C5|C6|C7|C8|C9},
};

// 盒子的組態
int box[9] = {C1, C2, C3, C4, C5, C6, C7, C8, C9};

typedef vector<int>     Rule;
typedef vector<Rule>    RuleSet;

// 驗證盒子裡的擺法，能否滿足某條指定規則
bool validate(Rule &rule)
{
    for (int i = 0, j; i < 9; i += 3) {     // 有 3 排，要分 3 次，每次 3 顆
        if (rule.size() == 3) {
            if ((rule[0] & box[i]) && (rule[1] & box[i+1]) && (rule[2] & box[i+2]))
                return true;
        } else {    // rule.size == 2  ==> 拆成左、右測試看看，滿足其中邊就可以了
            if (((rule[0] & box[i]) && (rule[1] & box[i+1]))
                || ((rule[0] & box[i+1]) && (rule[1] & box[i+2])))
                return true;
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, l;
    char cs[5] = {};
    RuleSet rule_list;
 
    cin >> n;

    rule_list.reserve(n);

    for (; n > 0; n--) {
        cin >> l;
        Rule    rule(l);
        for (int i = 0; i < l; i++) {
            cin >> cs[0] >> cs[1];
            rule[i] = RULEMAP[cs];
        }
        rule_list.push_back(rule);
    }

    int cnt = 0;
    do {
        cnt += all_of(rule_list.begin(), rule_list.end(), validate);    // 滿足所有規則的才加進來
        // if (all_of(rule_list.begin(), rule_list.end(), validate)) {
        //     cnt++;
        // }
    } while (next_permutation(box, box+9));
    cout << cnt << '\n';
    return 0;
}
```