题解：P7395 弹珠游戏（2021 CoE-I C）

OvO_CYX · 2025-12-17 12:57:44 · 题解

P7395 弹珠游戏（2021 CoE-I C） 题解

题目传送门

题意

写得非常清楚，不写了。

暴搜大法好！

我们将状态变成一个数，就可以进行记忆化搜索：对于每种状态，若状态 A 是一个必败态，那么其增加一步操作可以得到的状态 A+\alpha 就是一个必胜态。并且我们知道该图全为 * 时（即状态为 65535 时）是一个必败态。
我们先预处理出旋转 45\degree 下每一种情况的胜负，然后对于每次询问，用 O(1) 的复杂度将状态旋转 45\degree，并且去询问是否合法。
::::info[Code]

#include<bits/stdc++.h>
//#pragma GCC optimize (1,2,3,"Ofast","inline")
//#define int long long
//#define into into
using namespace std;
inline int read(){
    int res=0,f=1;
    char ch=getchar();
    for(;ch>57||ch<48;ch=getchar())if(ch=='-')f=-1;
    for(;ch>47&&ch<58;ch=getchar())res=(res<<1)+(res<<3)+(ch^48);
    return res*f;
}
struct node{int a[5][5];};
inline int calc(node x){
    int ss=0;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            ss+=(x.a[i][j]<<((i-1)*4+(j-1)));
    return ss;
}
int is[655360];
const int dx[]={0,1,0,1,1};
const int dy[]={0,0,1,1,-1};
inline node copy(node y){
    node x;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            x.a[i][j]=y.a[i][j];
    return x;
}
inline void dfs(node x){
    if(is[calc(x)]!=-1)return ;
    is[calc(x)]=0;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++){
            if(x.a[i][j])continue;
            x.a[i][j]=1;
            dfs(x);
            if(is[calc(x)]==0)
                x.a[i][j]=0,is[calc(x)]=1;
            else x.a[i][j]=0;
            for(int d=1;d<=4;d++){
                node y=copy(x);
                y.a[i][j]=1;
                int nx=i,ny=j;
                for(int cnt=1;cnt<=2;cnt++){
                    nx+=dx[d],ny+=dy[d];
                    if(x.a[nx][ny]||nx<1||ny<1||nx>4||ny>4)break;
                    y.a[nx][ny]=1;
                    dfs(y);
                    if(is[calc(y)]==0)
                        is[calc(x)]=1;
                }
            }
        }
    return ;
}
inline void init(){
    memset(is,-1,sizeof is);
    is[65535]=0;
    node x;
    memset(x.a,0,sizeof x.a);
    dfs(x);
    return ;
}
signed main(){
    init();
    int T;
    for(cin>>T;T--;){
        char ch;
        cin>>ch;
        int ss=(ch=='*');
        cin>>ch;
        ss+=(ch=='*')<<4;
        cin>>ch;
        ss+=(ch=='*')<<1;
        cin>>ch;
        ss+=(ch=='*')<<8;
        cin>>ch;
        ss+=(ch=='*')<<5;
        cin>>ch;
        ss+=(ch=='*')<<2;
        cin>>ch;
        ss+=(ch=='*')<<12;
        cin>>ch;
        ss+=(ch=='*')<<9;
        cin>>ch;
        ss+=(ch=='*')<<6;
        cin>>ch;
        ss+=(ch=='*')<<3;
        cin>>ch;
        ss+=(ch=='*')<<13;
        cin>>ch;
        ss+=(ch=='*')<<10;
        cin>>ch;
        ss+=(ch=='*')<<7;
        cin>>ch;
        ss+=(ch=='*')<<14;
        cin>>ch;
        ss+=(ch=='*')<<11;
        cin>>ch;
        ss+=(ch=='*')<<15;
        puts(is[ss]?"Possible.":"Impossible.");
    }
    return 0;
}

::::