http://www.lydsy.com/JudgeOnline/problem.php?id=1054

大意

在一个4*4的方框内摆放了若干个相同的玩具，将这些玩具重新摆放成为理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具。求最小移动次数。

题解

暴力BFS，因为格子很少，直接用位运算

萌神的写法非常厉害，看代码吧。

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=65536,
dx[24]={15,14,13,15,14,13,12,11,10,9,11,10,9,8,7,6,5,7,6,5,4,3,2,1},
dy[24]={14,13,12,11,10,9,8,10,9,8,7,6,5,4,6,5,4,3,2,1,0,2,1,0};
int q[N],d[N],S,T;

int main()
{
	memset(d,127,sizeof(d));
	for(int i=0;i<4;i++,getchar())
		for(int j=0;j<4;j++)
			S=(S<<1)+getchar()-'0';
	getchar();
	for(int i=0;i<4;i++,getchar())
		for(int j=0;j<4;j++)
			T=(T<<1)+getchar()-'0';
	if(S==T){puts("0");return 0;}
	d[S]=0;int l=0,r=1;q[1]=S;
	while(l<r)
	{
		int now=q[++l];
		for(int i=0;i<24;i++)
		{
			int x=now&(1<<dx[i]),y=now&(1<<dy[i]);
			int next=now-x-y;
			if(x)	next+=1<<dy[i];
			if(y)	next+=1<<dx[i];
			if(d[next]>d[now]+1)
			{
				d[next]=d[now]+1;
				q[++r]=next;
				if(next==T)
				{
					printf("%d\n",d[T]);
					return 0;
				}
			}
		}
	}
}