【題解】ZeroJudge a365: 3. 新井字遊戲

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

int t, dp[4100];
vector <int> v[15] = {{3}, {4}, {3}, {0, 2, 4, 7}, {1, 3, 5, 8}, {4}, {7}, {3, 6, 8, 10}, {4, 7, 9, 11}, {8}, {7}, {8}};
string s;

int f(int mask){
    if (dp[mask] != -1) return dp[mask];
    dp[mask] = 0;
    for (int i = 0; i < 12; i++){
        if (mask & (1<<i)){
            if (!f(mask-(1<<i))) dp[mask] = 1;
            for (auto j:v[i]){
                if (mask & (1<<j)){
                    if (!f(mask-(1<<i)-(1<<j))) dp[mask] = 1;
                }
            }
        }
    }
    return dp[mask];
}

int main() {
    cin >> t;
    while (t--){
        cin >> s;
        memset(dp, -1, sizeof(dp));
        int mask = 0;
        for (int i = 0; i < 12; i++){
            if (s[i] == '1') mask |= (1<<i);
        }
        dp[0] = 1;
        cout << f(mask);
    }
}