首页 > 代码库 > 【位运算】【BFS】移动玩具

【位运算】【BFS】移动玩具

2024-10-03 00:22:02   216人阅读

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2246  Solved: 1246
[Submit][Status][Discuss]

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

HINT

 

Source

 

试题分析：也许太闲的了，我竟然使位运算写这题(一时脑抽)……

               简简单单的BFS，正解再加个HASH搞定

               想想我这样好像还省了个Hash QAQ

 

代码(大神勿喷)

#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<stack>#include<vector>#include<algorithm>//#include<cmath>using namespace std;const int INF = 9999999;#define LL long longinline int read(){	int x=0,f=1;char c=getchar();	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;	return x*f;}int N,E;bool vis[65539];char c;int l=1,r=1;struct data{	int st,k;}Que[700001];void BFS(){	Que[l].st=0,Que[l].k=N;	int step,Now;	if(Que[l].k==E){		printf("%d\n",Que[l].st);		return ;	}	while(l<=r){		Now=Que[l].k,step=Que[l].st;		for(int i=1;i<=4;i++){			for(int j=1;j<=4;j++){				if(((Now>>((4-i)*4+4-j))&1)){					for(int p=0;p<4;p++){						if(p==0&&i!=1&&!((Now>>((4-(i-1))*4+4-j))&1)&&!vis[Now-(1<<((4-i)*4+4-j))+(1<<((4-i)*4+8-j))]){							Que[++r].k=Now-(1<<((4-i)*4+4-j))+(1<<((4-i)*4+8-j));							if(Que[r].k==E){								printf("%d\n",step+1);								return ;							}							Que[r].st=step+1;							vis[Que[r].k]=1;						}						if(p==1&&i!=4&&!((Now>>((4-(i+1))*4+4-j))&1)&&!vis[Now-(1<<((4-i)*4+4-j))+(1<<((4-i)*4-j))]){							Que[++r].k=Now-(1<<((4-i)*4+4-j))+(1<<((4-i)*4-j));							if(Que[r].k==E){								printf("%d\n",step+1);								return ;							}							Que[r].st=step+1;							vis[Que[r].k]=1;						}						if(p==2&&j!=1&&!((Now>>((4-i)*4+4-(j-1)))&1)&&!vis[(1<<((4-i)*4+4-j))+(1<<((4-i)*4+4-(j-1)))]){							Que[++r].k=Now-(1<<((4-i)*4+4-j))+(1<<((4-i)*4+4-(j-1)));							if(Que[r].k==E){								printf("%d\n",step+1);								return ;							}							Que[r].st=step+1;							vis[Que[r].k]=1;						}						if(p==3&&j!=4&&!((Now>>((4-i)*4+4-(j+1)))&1)&&!vis[Now-(1<<((4-i)*4+4-j))+(1<<((4-i)*4+4-(j+1)))]){							Que[++r].k=Now-(1<<((4-i)*4+4-j))+(1<<((4-i)*4+4-(j+1)));							if(Que[r].k==E){								printf("%d\n",step+1);								return ;							}							Que[r].st=step+1;							vis[Que[r].k]=1;						}					}				}			}		}				l++;	}}int main(){	//freopen(".in","r",stdin);	//freopen(".out","w",stdout);	int tmp=16;	for(int i=1;i<=4;i++)	    for(int j=1;j<=4;j++){	    	cin>>c;	    	N=N+(1<<(tmp-1))*(c-‘0‘);	    	tmp--;		}	vis[N]=true;	tmp=16;	for(int i=1;i<=4;i++)	    for(int j=1;j<=4;j++){	    	cin>>c;	    	E=E+(1<<(tmp-1))*(c-‘0‘);	    	tmp--;		}	BFS();	return 0;}

　　

【位运算】【BFS】移动玩具


联系
我们