题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=1054很多写法，我写的是SPFA+Hash。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MaxN=(1<<16)+10;
const int dx[4]=
{-1,1,-4,4};
int s=0,t=0,f[MaxN];
void init()
{
for (int i=0;i<16;i++)
{
char x;
cin>>x;
s=(s<<1)+(x-'0');
}
//cout<<s<<endl;
for (int i=0;i<16;i++)
{
char x;
cin>>x;
t=(t<<1)+(x-'0');
}
//cout<<t<<endl;
}
int q[MaxN],a[16];
bool vis[MaxN];
int hash(int *a)
{
int ans=0;
for (int i=0;i<16;i++)
{
ans=(ans<<1)+a[i];
}
return ans;
}
int work()
{
memset(f,-1,sizeof(f));
memset(vis,0,sizeof(vis));
f[s]=0;
vis[s]=1;
q[0]=s;
for (int first=0,last=1;first!=last;first++)
{
//system("pause");
//cout<<q[first]<<endl;
if (first>=MaxN)
{
first-=MaxN;
}
if (q[first]==t)
{
return f[t];
}
int x=q[first];
for (int i=15;i>=0;i--)
{
a[i]=x%2;
x/=2;
}
for (int i=0;i<16;i++)
{
//cout<<a[i];
//if (i%4==3) cout<<endl;
if (a[i]==1)
{
for (int j=0;j<4;j++)
{
if ((j==0 && i%4==0) || (j==1 && i%4==3))
{
continue;
}
if (i+dx[j]>=0 && i+dx[j]<16 && a[i+dx[j]]==0)
{
a[i]=0;
a[i+dx[j]]=1;
int k=hash(a);
if (f[k]==-1 || f[k]>f[q[first]]+1)
{
f[k]=f[q[first]]+1;
if (vis[k]==0)
{
q[last++]=k;
if (last>=MaxN)
{
last-=MaxN;
}
}
}
a[i]=1;
a[i+dx[j]]=0;
}
}
}
}
vis[q[first]]=0;
}
}
int main()
{
init();
cout<<work()<<endl;
return 0;
}