[BZOJ]1054: [HAOI2008]移动玩具BFS

2017-01-03 19:13:56来源:CSDN作者:baidu_36797646人点击

第七城市

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

BFS水题,不解释直接放代码。

#include<cstdio>#include<cstring>const int Q=66666;struct zt{	int a[5],t;}q[Q];int end[5];bool h[16][16][16][16];bool have_one(int st,int n,int m){	int t=(1<<(4-m));	if((q[st].a[n]&t)>0) return true;	return false;}bool is(int x,int y){	if(x<1 || y<1 || x>4 || y>4) return false;	return true;}int tx[]={0,0,1,-1};int ty[]={1,-1,0,0};int main(){	memset(h,false,sizeof(h));	char s[5][5];	for(int i=1;i<=4;i++)	{		scanf("%s",s[i]);		for(int j=0;j<4;j++)		q[1].a[i]+=(1<<(3-j))*(s[i][j]-'0');	}	q[1].t=0;h[q[1].a[1]][q[1].a[2]][q[1].a[3]][q[1].a[4]]=true;	for(int i=1;i<=4;i++)	{		scanf("%s",s[i]);		for(int j=0;j<4;j++)		end[i]+=(1<<(3-j))*(s[i][j]-'0');	}	int st=1,ed=2;	while(st<=ed)	{		bool right=true;		for(int i=1;i<=4;i++)		if(q[st].a[i]!=end[i])		{			right=false;			break;		}		if(right==true)		{			printf("%d",q[st].t);			break;		}		for(int i=1;i<=4;i++)		for(int j=1;j<=4;j++)		if(have_one(st,i,j)==true)		{			for(int k=0;k<4;k++)			{				int nx=i+tx[k],ny=j+ty[k];				if(is(nx,ny)==true && have_one(st,nx,ny)==false)				{					int xx=q[st].a[i],yy=q[st].a[nx];					q[st].a[i]-=(1<<(4-j));q[st].a[nx]+=(1<<(4-ny));					if(h[q[st].a[1]][q[st].a[2]][q[st].a[3]][q[st].a[4]]==false)					{						h[q[st].a[1]][q[st].a[2]][q[st].a[3]][q[st].a[4]]=true;						q[ed]=q[st];						q[ed].t++;						ed++;					}					q[st].a[i]=xx;q[st].a[nx]=yy;				}			}		}		st++;	}}


第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台