2017-2018 ACM-ICPC, Asia Daejeon Regional Contest B - Connect3

問題ページ
盤面のマスは なし/黒/白 の3通りで16マスなので 通りしか存在しない．注意してDFSを実装すると状態数が少ないので間に合う．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int trans(vector<int> field) {  
    int ret = 0;  
    for(auto i: field) {  
        ret *= 3;  
        ret += i;  
    }  
    assert(ret < 43046721);  
    return ret;  
}  
  
int ans[16];  
bool used[43046721];  
void dfs(vector<int> field, int turn) {  
    int hs = trans(field);  
    used[hs] = true;  
    REP(x, 4) {  
        ll y=-1;  
        for(y=3; y>=0; --y) if(field[y*4+x] == 0) break;  
        if(y == -1) continue;  
        field[y*4+x] = turn+1;  
  
        bool fin = false;  
        REP(i, 2) REP(j, 4) {  
            if(field[i*4+j] && field[i*4+j]==field[(i+1)*4+j] && field[i*4+j]==field[(i+2)*4+j]) {  
                fin = true;  
            }  
        }  
        REP(i, 4) REP(j, 2) {  
            if(field[i*4+j] && field[i*4+j]==field[i*4+j+1] && field[i*4+j]==field[i*4+j+2]) {  
                fin = true;  
            }  
        }  
        REP(i, 2) REP(j, 2) {  
            if(field[i*4+j] && field[i*4+j]==field[(i+1)*4+j+1] && field[i*4+j]==field[(i+2)*4+j+2]) {  
                fin = true;  
            }  
        }  
        REP(i, 2) FOR(j, 2, 4) {  
            if(field[i*4+j] && field[i*4+j]==field[(i+1)*4+j-1] && field[i*4+j]==field[(i+2)*4+j-2]) {  
                fin = true;  
            }  
        }  
  
        if(fin) {  
            if(turn == 1) ans[y*4+x]++;  
            field[y*4+x] = 0;  
            continue;  
        }  
        if(used[trans(field)]) {  
            field[y*4+x] = 0;  
            continue;  
        }  
  
        dfs(field, 1-turn);  
        field[y*4+x] = 0;  
    }  
}  
  
int main(void) {  
    ll sx;  
    cin >> sx;  
    sx--;  
  
    vector<int> field(16);  
    field[12+sx] = 1;  
    dfs(field, 1);  
  
    ll a, b;  
    cin >> a >> b;  
    a--, b--;  
    a = 3-a;  
  
    cout << ans[a*4+b] << endl;  
  
    return 0;  
}