bzoj1054 [HAOI2008]移动玩具

浏览数：31 / 时间：2015年06月11日

Description

在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

Input

前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。

Output

一个整数，所需要的最少移动次数。

Sample Input

1111
0000
1110
0010

1010
0101
1010
0101

Sample Output

唉一道sb的搜索写的我累觉不爱

#include<cstdio>
#include<iostream>
#define LL long long
const int mx[4]={1,0,-1,0};
const int my[4]={0,1,0,-1};
const int v[4][4]={{1,2,4,8},{16,32,64,128},{256,512,1024,2048},{4096,8192,16384,32768}};
struct que{
	int a[4][4],step,rnk;
}q[100010],s,e;
bool mrk[100010];
int t,w=1,nx,ny;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
inline int getrnk(que a)
{
	int tot=0,mul=1;
	for (int i=0;i<4;i++)
	for (int j=0;j<4;j++)
	{
		if (a.a[i][j])tot+=mul;
		mul*=2;
	}
	return tot;
}
inline void ini(que &a)
{	
	for (int i=0;i<4;i++)
	for (int j=0;j<4;j++)
	{
		char ch=getchar();
		while (ch!=‘0‘&&ch!=‘1‘)ch=getchar();
		if(ch==‘1‘)a.a[i][j]=1;
	}
}
int main()
{
	ini(s);
	ini(e);
	q[1]=s;q[1].rnk=getrnk(s);
	mrk[q[1].rnk]=1;
	e.rnk=getrnk(e);
	if(e.rnk==q[1].rnk)
	{
		printf("0");
		return 0;
	}
	while (t<w)
	{
		que now=q[++t];now.step++;
		for (int i=0;i<4;i++)
		for (int j=0;j<4;j++)
		if (now.a[i][j])
			for (int k=0;k<4;k++)
			{
				nx=i+mx[k];ny=j+my[k];
				if (nx<0||nx>3||ny<0||ny>3||now.a[nx][ny])continue;
				now.rnk+=v[nx][ny]-v[i][j];
				if (mrk[now.rnk])
				{
					now.rnk-=v[nx][ny]-v[i][j];
					continue;
				}
				if (now.rnk==e.rnk)
				{
					printf("%d\n",now.step);
					return 0;
				}
				now.a[i][j]=0;now.a[nx][ny]=1;
				q[++w]=now;mrk[now.rnk]=1;
				now.a[i][j]=1;now.a[nx][ny]=0;
				now.rnk-=v[nx][ny]-v[i][j];
			}
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

bzoj1054 [HAOI2008]移动玩具