状压bfs
一共有16个位置，最多会有 2^{16}=65536种情况，用数组完全开的下。

用二进制中的1表示该位置有玩具，0表示该位置没有玩具。

由于广搜最先搜到的是最优解，直接用数组记录是否到达过该状态，顺便记录ans.

移动前的状态ans为0.

然后大力讨论12种情况即可

时间复杂度O( 2^{16} ) O(能过)

献上我又臭又长的代码

```cpp

include

include

include

include

using namespace std;
int z[524289],pan[524289];
int a,b,d;
char c;
queueq;
int ex(int s,int li,int ri)
{
return (s^(1<<li))^(1<<ri);
}
void fang(int xx,int fa)
{
if(pan[xx]==0)
{
pan[xx]=1;
z[xx]=z[fa]+1;
q.push(xx);
}
}
int main()
{
//freopen("toy.in","r",stdin);
//freopen("toy.out","w",stdout);
for(int i=1;i<=16;++i)
{
cin>>c;
a=(a<<1)|(c-‘0‘);
}
for(int i=1;i<=16;++i)
{
cin>>c;
b=(b<<1)|(c-‘0‘);
}
if(a==b)
{
cout<<"0";
return 0;
}
pan[a]=1;
q.push(a);
while(!q.empty())
{
int x=0;
d=q.front();
q.pop();
if(d&(1<<15))//1号位
{
if((d&(1<<14))==0)
{
x=ex(d,15,14);
fang(x,d);
}
if((d&(1<<11))==0)
{
x=ex(d,15,11);
fang(x,d);
}
}
for(int i=2;i<=3;++i)//2~3号位
{
if(d&(1<<(16-i)))
{
if((d&(1<<(16-i+1)))==0)
{
x=ex(d,16-i,16-i+1);
fang(x,d);
}
if((d&(1<<(16-i-1)))==0)
{
x=ex(d,16-i,16-i-1);
fang(x,d);
}
if((d&(1<<(16-i-4)))==0)
{
x=ex(d,16-i,16-i-4);
fang(x,d);
}
}
}
if(d&(1<<12))//4号位
{
if((d&(1<<13))==0)
{
x=ex(d,13,12);
fang(x,d);
}
if((d&(1<<8))==0)
{
x=ex(d,12,8);
fang(x,d);
}
}
if(d&(1<<11))//5号位
{
if((d&(1<<15))==0)
{
x=ex(d,15,11);
fang(x,d);
}
if((d&(1<<10))==0)
{
x=ex(d,10,11);
fang(x,d);
}
if((d&(1<<7))==0)
{
x=ex(d,7,11);
fang(x,d);
}
}
for(int i=6;i<=7;++i)//6~7号位
{
if(d&(1<<(16-i)))
{
if((d&(1<<(16-i+4)))==0)
{
x=ex(d,16-i,16-i+4);
fang(x,d);
}
if((d&(1<<(16-i+1)))==0)
{
x=ex(d,16-i,16-i+1);
fang(x,d);
}
if((d&(1<<(16-i-1)))==0)
{
x=ex(d,16-i,16-i-1);
fang(x,d);
}
if((d&(1<<(16-i-4)))==0)
{
x=ex(d,16-i,16-i-4);
fang(x,d);
}
}
}
if(d&(1<<8))//8号位
{
if((d&(1<<12))==0)
{
x=ex(d,8,12);
fang(x,d);
}
if((d&(1<<9))==0)
{
x=ex(d,8,9);
fang(x,d);
}
if((d&(1<<4))==0)
{
x=ex(d,8,4);
fang(x,d);
}
}
if(d&(1<<7))//9号位
{
if((d&(1<<11))==0)
{
x=ex(d,7,11);
fang(x,d);
}
if((d&(1<<6))==0)
{
x=ex(d,7,6);
fang(x,d);
}
if((d&(1<<3))==0)
{
x=ex(d,7,3);
fang(x,d);
}
}
for(int i=10;i<=11;++i)//10~11号位
{
if(d&(1<<(16-i)))
{
if((d&(1<<(16-i+4)))==0)
{
x=ex(d,16-i,16-i+4);
fang(x,d);
}
if((d&(1<<(16-i+1)))==0)
{
x=ex(d,16-i,16-i+1);
fang(x,d);
}
if((d&(1<<(16-i-1)))==0)
{
x=ex(d,16-i,16-i-1);
fang(x,d);
}
if((d&(1<<(16-i-4)))==0)
{
x=ex(d,16-i,16-i-4);
fang(x,d);
}
}
}
if(d&(1<<4))//12号位
{
if((d&(1<<8))==0)
{
x=ex(d,8,4);
fang(x,d);
}
if((d&(1<<5))==0)
{
x=ex(d,4,5);
fang(x,d);
}
if((d&(1<<0))==0)
{
x=ex(d,4,0);
fang(x,d);
}
}
if(d&(1<<3))//13号位
{
if((d&(1<<7))==0)
{
x=ex(d,3,7);
fang(x,d);
}
if((d&(1<<2))==0)
{
x=ex(d,3,2);
fang(x,d);
}
}
for(int i=14;i<=15;++i)//14~15号位
{
if(d&(1<<(16-i)))
{
if((d&(1<<(16-i+4)))==0)
{
x=ex(d,16-i,16-i+4);
fang(x,d);
}
if((d&(1<<(16-i+1)))==0)
{
x=ex(d,16-i,16-i+1);
fang(x,d);
}
if((d&(1<<(16-i-1)))==0)
{
x=ex(d,16-i,16-i-1);
fang(x,d);
}
}
}
if(d&(1<<0))//16号位
{
if((d&(1<<1))==0)
{
x=ex(d,0,1);
fang(x,d);
}
if((d&(1<<4))==0)
{
x=ex(d,4,0);
fang(x,d);
}
}
}
cout<<z[b];
fclose(stdin);fclose(stdout);
return 0;
}

bzoj 1054: [HAOI2008]移动玩具

原文：https://www.cnblogs.com/wljss/p/11482572.html