题解 [HAOI2008] 移动玩具

题意

题目链接：传送门

题目大意是给两个\(4*4\)的\(01\)矩阵\(A,B\),求至少对矩阵\(A\)中任意元素进行上下左右移动多少次后能使得\(A=B\)

Solution

碎碎念：不知道当时考试是不是时限给的\(100ms\)(应该是吧)

先考虑暴力做法，自然地想到把矩阵变成\(01\)串状态压缩，\(2^{16}=65536\)，可以直接用哈希判重，bfs即可。

注意一下模拟移动的细节和边界情况。

然后这个暴力有可能会T掉（其实卡一卡好像并不会）

还是来考虑一下优化好了。。。。

显然可以\(A*\),估价函数设计为\(status\ xor\ target\),其中\(status\)表示当前状态，\(target\)表示目标状态，即求目前有多少位与目标状态不同，容易证明其正确性。

某谷上一共跑了约\(20ms\)，\(LOJ\)上莫名跑的比暴力还慢。。。。

后来做了几个测试，发现暴力好像跑的的确很快。。。省选为什么考爆搜（大雾

附代码：

#include
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
using namespace std;
typedef long long ll;
template  inline void read(T &x){
	ll f = 1;x = 0;char ch = getchar();
	while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}
	while (isdigit(ch)){x = (x << 1)+(x << 3)+(ch ^ 48);ch = getchar();}
	x *= f;
}

struct node
{
	int eva,step,sta;
	bool operator < (const node &X) const
	{
		return eva==X.eva?step>X.step:eva>X.eva;
	}
}Now;

int targt,init;
bool vis[65536];
priority_queue Q;

inline void _get(int &x)
{
	char c;
	rep(i,1,16)
	{
		cin>>c;
		x=(x<<1)+c-'0';
	}
}

inline int evaluate(int sta)
{
	int dif=sta^targt;
	int res=0;
	while(dif)
	{
		res+=dif&1;
		dif>>=1;	
	}
	return res;
}

int u[4]={4,-4,1,-1};

inline int move(int sta,int pos,int opt)
{
	int x=(sta>>pos)&1,y=(sta>>(pos+u[opt]))&1;
	if(y==0)sta=sta&(~(1<>i)&1))continue;
			rep(j,0,3)
			{
				if(j==0&&i>11||j==1&&i<4||j==2&&i%4==3||j==3&&i%4==0)continue;
				int x=move(fi.sta,i,j);
				
				if(!vis[x])
				{
					vis[x]=1;
					Now.step=fi.step+1;
					Now.sta=x;
					Now.eva=Now.step+evaluate(x);
					if(Now.eva==Now.step)
					{
						printf("%d",Now.step);
						return; 
					} 
					Q.push(Now);
				}
			}
		}
	}
}
int main()
{
	
	_get(init),_get(targt);

	if(init==targt)
	{
		cout<<0<