题解 | 弹珠游戏

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=10100,mod=998244353;
int dp[(1<<16)+10];
int g[5][5]={
    {0,0,0,0,0},
    {0,1,3,6,10},
    {0,2,5,9,13},
    {0,4,8,12,15},
    {0,7,11,14,16}
};
vector<int> e;
int get2(int a,int b) {
    int ans=0;
    ans|=(1<<(a-1));
    ans|=(1<<(b-1));
    return ans;
}
int get3(int a,int b,int c) {
    int ans=0;
    ans|=(1<<(a-1));
    ans|=(1<<(b-1));
    ans|=(1<<(c-1));
    return ans;
}
void init() {
    for (int i=0;i<=(1<<16);i++)
        dp[i]=-1;
    dp[(1<<16)-1]=0;
    for (int i=1;i<=4;i++) {//预处理出所有可能进行的操作
        for (int j=1;j<=4;j++) {
            e.push_back(1<<(g[i][j]-1));
            if (j<=3) e.push_back(get2(g[i][j],g[i][j+1]));
            if (i<=3) e.push_back(get2(g[i][j],g[i+1][j]));
            if (j<=2) e.push_back(get3(g[i][j],g[i][j+1],g[i][j+2]));
            if (i<=2) e.push_back(get3(g[i][j],g[i+1][j],g[i+2][j]));
            if (i+1<=4&&j+1<=4) e.push_back(get2(g[i][j],g[i+1][j+1]));
            if (i+1<=4&&j-1>=1) e.push_back(get2(g[i][j],g[i+1][j-1]));
            if (i+2<=4&&j+2<=4) e.push_back(get3(g[i][j],g[i+1][j+1],g[i+2][j+2]));
            if (i+2<=4&&j-2>=1) e.push_back(get3(g[i][j],g[i+1][j-1],g[i+2][j-2]));
        }
    }
}

void solve() {
    int x=0;
    for (int i=0;i<16;i++) {
        char c;
        cin>>c;
        if (c=='*') x|=(1<<i);
    }
    auto dfs=[&](auto &self,int x)->int {
        if (dp[x]!=-1) return dp[x];
        for (auto it:e) {//枚举所有可能操作
            if (x&it) continue;//与当前局面重复则不行
            if (!self(self,x|it))
                return dp[x]=1;
        }
        dp[x]=0;
        return dp[x];
    };
    if (dfs(dfs,x)) cout<<"Alice"<<endl;
    else cout<<"Bob"<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int t=1;
    cin>>t;
    while(t--)solve();
}

把每一个状态转换成一个二进制数，然后转成十进制进行记忆化搜索。如果当前进行某种操作后为必败态，当前则为必胜态；若没有必败态则当前为必败态。