自动搬运

查看原文

来自洛谷，原作者为

	cmll02 Pub txdy

搬运于2025-08-24 22:29:27，当前版本为作者最后更新于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.");
	}
}