NULL

cmll02 · 2021-02-25 09:52:18 · 题解

一共就 65536 种不同状态，我直接状态压缩再打表！

棋盘斜的比较难受，转 45\degree 就行了。

走棋还是横竖斜都可以。

首先写个 dfs 来出表：（注意记忆化）

预处理 65535 是必败态，然后就有了如下：

#include <stdio.h>
#include <string.h>
struct state{
    int a[4][4];
    state operator=(state b)
    {
        memcpy(a,b.a,sizeof(int)*16);
    }
    int operator()()
    {
        int num=0;
        int p=1;
        for(int i=3;~i;i--)
            for(int j=3;~j;j--)
                num+=p*a[i][j],p<<=1;
        return num;
    }
};
int mmr[1<<16+5];
int dir[4][2]={1,0,0,1,1,1,1,-1};
#define s x.a
int cnt=0;
void dfs(state x)
{
    if(mmr[x()]!=-1)return;
    mmr[x()]=0;
    cnt++;
    //printf("%d\n",x());
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(x.a[i][j])continue;
            x.a[i][j]=1;
            dfs(x);
            if(mmr[x()]==0)
            {
                x.a[i][j]=0;
                mmr[x()]=1;
            }
            x.a[i][j]=0;
            for(int d=0;d<4;d++)
            {
                state p=x;
                p.a[i][j]=1;
                int ii=i,jj=j;
                for(int iii=0;iii<2;iii++)
                {
                    ii+=dir[d][0],jj+=dir[d][1];
                    if(x.a[ii][jj]||ii<0||jj<0||ii>3||jj>3)break;
                    p.a[ii][jj]=1;
                    dfs(p);
                    if(mmr[p()]==0)
                    {
                        mmr[x()]=1;
                    }
                }
            }
        }
    }
}
#undef s
int main()
{
    memset(mmr,-1,sizeof(mmr));
    mmr[65535]=0;
    state s;
    memset(s.a,0,sizeof(int)*16);
    dfs(s);
    freopen("ChuLeWoYiWaiDeSuoYouRenDouAKIOI.orz","w",stdout);
    for(int i=0;i<65536;i++)printf("%d",mmr[i]);
}

然后就出现了一个表。

直接扔到字符串里一交。

然后一看，这个表有 65536 个 0 或 1，太占代码空间。

于是随便三个数二进制压缩一下：（这里我在原来的文件后面加了两个 0）

#include <stdio.h>
int main()
{
    freopen("ChuLeWoYiWaiDeSuoYouRenDouAKIOI.orz","r",stdin);
    freopen("ChuLeWoYiWaiDeSuoYouRenDouAKIOI.sto","w",stdout);
    for(int i=0;i<65538/3;i++)
    {
        int aaaa=getchar()-48;
        int aa=getchar()-48;
        int a=getchar()-48;
        printf("%d",aaaa*4+aa*2+a);
    }
}

然后就能交了。最终代码：

#include <stdio.h>
char c[]="之前生成的表，由于太大我没放下来。";
int cc=0;
inline int w(int x)
{
    char c=getchar();
    while(c!='*'&&c!='.')c=getchar();
    if(c=='*')cc+=(1<<x);
}//状态压缩
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cc=0;
        w(3);
        w(2);
        w(7);
        w(1);
        w(6);
        w(11);
        w(0);
        w(5);
        w(10);
        w(15);
        w(4);
        w(9);
        w(14);
        w(8);
        w(13);
        w(12);
        int qaq=(c[cc/3]-48)>>(2-cc%3);
        qaq&=1;
        if(qaq)puts("Possible.");
        else puts("Impossible.");
    }
}