时间戳

首页 > 技术文章 > bzoj1054 [HAOI2008]移动玩具

bzoj1054 [HAOI2008]移动玩具

zhber 2014-11-29 17:43 原文

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

4

唉一道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;
}

　　

推荐阅读