题解 | 弹珠游戏

//使用0，1编码位置是否被占据，使用位运算进行搜索
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
//棋盘状态记录
vector<int> rec;
//记忆化搜索
unordered_map<int, bool> memo;
//读入顺序映射到标准数组的位置
const int arr[16]={0,2,5,9, 1,4,8,12, 3,7,11,14, 6,10,13,15};
void record(){
    rec.clear();
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            int m0=1<<(4*i+j);
            rec.push_back(m0);
            int m1=m0,m2=m0,m3=m0,m4=m0;
            for(int l=1;l<3;l++){
                if(i+l<4){
                    m1+=1<<(4*(i+l)+j);
                    rec.push_back(m1);
                }if(j+l<4){
                    m2+=1<<(4*i+j+l);
                    rec.push_back(m2);
                }if((i+l<4)&&(j+l<4)){
                    m3+=1<<(4*(i+l)+j+l);
                    rec.push_back(m3);
                }if((i+l<4)&&(j-l>=0)){
                    m4+=1<<(4*(i+l)+j-l);
                    rec.push_back(m4);
                }
            }
        }
    }
}
bool Win(int mask, const vector<int>& moves) {
    if (memo.count(mask)) return memo[mask];
    for (int move : moves) {
        if ((mask & move) == 0) {
            if (!Win(mask | move, moves)) {
                return memo[mask] = true;
            }
        }
    }
    return memo[mask] = false;
}
void solve(){
    char p[16];
    int q[16];
    for(int i=0;i<16;i++){
        cin>>p[i];
    }for(int i=0;i<16;i++){
        q[i]=(p[arr[i]]=='.')?0:1;
    }int tar=0;
    for(int i=0;i<16;i++){
        tar=(tar<<1)+q[i];
    }if(Win(tar,rec)){
        cout<<"Alice"<<endl;
    }else{
        cout<<"Bob"<<endl;
    }
}
int main(){
    int T;
    cin>>T;
    while(T--){
        record();
        solve();
    }
    return 0;
}