[BalticOI 2002 Day2] L Game © Edward de Bono

樱雪喵 · 2024-01-04 15:35:19 · 题解

调了 2.5h，比去年省选的时候有点进步 /cf

一眼看起来是有三种胜负态的爆搜，神似 [省选联考 2023] 过河卒。给题解打广告 >w<

题里告诉我们状态数只有 18000 多种，也就是说直接暴力把状态转移图建出来是可行的。但是有环怎么判平局呢？

倒序拓扑转移，一个点可以入队当且仅当：

• 它存在至少一个必败的出边；
• 它所有的出边胜负态都已经被确定。

依次确定胜负状态，若初始状态最后仍没有入过队，则平局。

然后剩下的就是大模拟了。卡常技巧：

• 对于 L 形棋，相比于记录一个点和 8 个方向（这有大量的不合法需要特判），记录 2\times 3 的矩形和 4 个方向是更优的选择；
• 用二进制而不是奇怪 hash 对状态直接压缩；
• map 很慢，如果用了奇怪 hash 建议手写哈希表；
• 两个中立点没有差别，钦定坐标较小的在前面可以减少一半状态；
• 钦定第一个棋子为先手，省去记录先后手的两倍状态常数。

本人代码踩遍了以上所有坑，喜提最劣解，建议不要参考。

#include<bits/stdc++.h>
#define il inline
using namespace std;
il long long read()
{
    long long xr=0,F=1; char cr;
    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
    while(cr>='0'&&cr<='9') 
        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
    return xr*F;
}
#define int long long
const int N=6,M=1e5+15;
const int mod=1000019;
int tot,bck[M];
struct hashtable
{

    struct edge{int nxt,x,w;} e[mod+5];
    int head[mod+5],cnt;
    il int find(int x)
    {
        for(int i=head[x%mod];i;i=e[i].nxt) if(e[i].x==x) return e[i].w;
        tot++; e[++cnt]={head[x%mod],x,tot},head[x%mod]=cnt,bck[tot]=x; return tot;
    }
}Mp;
char s[N][N];
struct node
{
    int op;
    struct L {int x,y,tp;} l[2];
    struct X {int x,y;} x[2];
    node() {memset(x,-1,sizeof(x)),memset(l,-1,sizeof(l)),op=-1;}
};
int ans[M],vis[M];
vector<int> e[M],E[M];
il node trans(int x)
{
    x=bck[x]; node a;
    for(int i=1;i>=0;i--) a.x[i].y=x%10,x/=10,a.x[i].x=x%10,x/=10;
    for(int i=1;i>=0;i--) a.l[i].tp=x%10,x/=10,a.l[i].y=x%10,x/=10,a.l[i].x=x%10,x/=10;
    a.op=x%10;
    return a;
}
int dx[8][4],dy[8][4];
int c[N][N];
int cx[4]={-1,0,1,0},cy[4]={0,1,0,-1};
il void write(int x)
{
    node a=trans(x);
    memset(c,-1,sizeof(c));
    for(int i=0;i<=1;i++)
    {
        for(int j=0;j<4;j++)
        {
            int x=a.l[i].x+dx[a.l[i].tp][j],y=a.l[i].y+dy[a.l[i].tp][j];
            c[x][y]=i; 
        }
        int x=a.x[i].x,y=a.x[i].y;
        c[x][y]=2; 
    }
    for(int i=0;i<4;i++,printf("\n"))
        for(int j=0;j<4;j++) 
        {
            if(c[i][j]==-1) printf(".");
            else if(c[i][j]==0) printf("*");
            else if(c[i][j]==1) printf("#");
            else printf("x");
        }
}
il int hsh(node a)
{
    int res=a.op;
    if(a.x[0].x>a.x[1].x||(a.x[0].x==a.x[1].x&&a.x[0].y>a.x[1].y)) swap(a.x[0],a.x[1]);
    for(int i=0;i<=1;i++) res=res*10+a.l[i].x,res=res*10+a.l[i].y,res=res*10+a.l[i].tp;
    for(int i=0;i<=1;i++) res=res*10+a.x[i].x,res=res*10+a.x[i].y;

    return Mp.find(res);
}
il void init()
{
    dx[0][0]=0,dy[0][0]=0; dx[0][1]=-1,dy[0][1]=0; dx[0][2]=-2,dy[0][2]=0; dx[0][3]=0,dy[0][3]=1;
    for(int i=0;i<=3;i++) dx[1][i]=-dx[0][i],dy[1][i]=dy[0][i];
    for(int i=0;i<=3;i++) dx[2][i]=-dx[0][i],dy[2][i]=-dy[0][i];
    for(int i=0;i<=3;i++) dx[3][i]=dx[0][i],dy[3][i]=-dy[0][i];
    for(int j=4;j<8;j++) for(int i=0;i<=3;i++) dx[j][i]=dy[j-4][i],dy[j][i]=dx[j-4][i];
}
il bool check(node a)
{
    memset(c,-1,sizeof(c));
    for(int i=0;i<=1;i++)
    {
        for(int j=0;j<4;j++)
        {
            int x=a.l[i].x+dx[a.l[i].tp][j],y=a.l[i].y+dy[a.l[i].tp][j];
            if(x<0||x>=4||y<0||y>=4||c[x][y]!=-1) return 0;
            c[x][y]=i; 
        }
        int x=a.x[i].x,y=a.x[i].y;
        if(x<0||x>=4||y<0||y>=4||c[x][y]!=-1) return 0;
        c[x][y]=i; 
    }
    return 1;
}
int out[M],in[M],to[M];
void build(node s)
{
    queue<node> q; q.push(s);
    while(!q.empty())
    {
        node u=q.front(); q.pop(); int hu=hsh(u);
        for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            for(int tp=0;tp<8;tp++) 
            {
                node nxt=u; nxt.l[u.op]={i,j,tp},nxt.op=u.op^1;
                if((i==u.l[u.op].x&&j==u.l[u.op].y&&tp==u.l[u.op].tp)||!check(nxt)) continue;
                for(int id=0;id<=1;id++)
                for(int x=0;x<4;x++)   
                    for(int y=0;y<4;y++)
                    {
                        node nxt=u; nxt.l[u.op]={i,j,tp},nxt.op=u.op^1;
                        nxt.x[id]={x,y};
                        if(check(nxt)) 
                        {
                            int h=hsh(nxt);
                            e[h].push_back(hsh(u)),out[hu]++;
                            E[hu].push_back(h);
                            if(!vis[h]) 
                            {
                                vis[h]=1;
                                q.push(nxt);
                            } 
                        }
                    }
            }
    }
}
il void solve()
{
    queue<int> q;
    for(int i=1;i<=tot;i++) if(!out[i]) q.push(i);
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        if(ans[u]!=-1) continue;
        for(auto v:E[u]) if(!ans[v]) {ans[u]=1,to[u]=v;break;}
        if(ans[u]==-1) ans[u]=0;
        for(auto v:e[u]) {out[v]--;if((!out[v]||ans[u]==0)&&ans[v]==-1) out[v]=0,q.push(v);}
    }
}
signed main()
{
    for(int i=0;i<4;i++) scanf("%s",s[i]);
    node st; init();
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            if(s[i][j]=='x') 
            {
                if(st.x[0].x==-1) st.x[0]={i,j};
                else st.x[1]={i,j}; continue;
            }
            if(s[i][j]=='.') continue;
            int qwq=0;
            for(int w=0;w<4;w++) 
            {
                int x=i+cx[w],y=j+cy[w];
                if(x<0||x>=4||y<0||y>=4) continue;
                if(s[x][y]==s[i][j]) qwq++;
            }
            if(qwq!=2) continue;
            for(int tp=0;tp<8;tp++)
            {
                bool flag=1;
                for(int J=0;J<4;J++)
                {
                    int x=i+dx[tp][J],y=j+dy[tp][J];
                    if(x<0||x>=4||y<0||y>=4||s[x][y]!=s[i][j]) flag=0;
                }
                if(flag) {st.l[s[i][j]=='#']={i,j,tp};break;}
            }
        }
    st.op=1;
    build(st);
    memset(ans,-1,sizeof(ans));
    solve();
    int hst=hsh(st);
    if(ans[hst]!=1) 
    {
        printf("No winning move\n");
        if(ans[hst]==-1) printf("Draw\n");
        else printf("Losing\n");
        return 0;
    }
    write(to[hst]);
    return 0;
}