【BZOJ1054】移动玩具（搜索）
题面
题解
这种小清新搜索题写出来好舒服啊。
要是原来的我来写代码肯定又臭又长吧。。
#include<cstdio>
#include<queue>
using namespace std;
queue<int> Q;
int pw[16],st[1<<16];
bool vis[1<<16];
void add(int u,int v){if(vis[v])return;vis[v]=true;st[v]=st[u]+1;Q.push(v);}
int main()
{
int S=0,x,T=0;
for(int i=0;i<16;++i)pw[i]=1<<i;
for(int i=0;i<16;++i)scanf("%1d",&x),S|=x<<i;
for(int i=0;i<16;++i)scanf("%1d",&x),T|=x<<i;
Q.push(S);vis[S]=true;
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int i=0;i<16;++i)
{
if(!(u&pw[i]))continue;
if(i>3&&!(u&pw[i-4]))add(u,u^pw[i-4]^pw[i]);
if(i<12&&!(u&pw[i+4]))add(u,u^pw[i+4]^pw[i]);
if(i%4&&!(u&pw[i-1]))add(u,u^pw[i-1]^pw[i]);
if(i%4!=3&&!(u&pw[i+1]))add(u,u^pw[i+1]^pw[i]);
}
if(vis[T])break;
}
printf("%d\n",st[T]);
return 0;
}