bzoj1054

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=‘ ‘;
    while(!isdigit(ch))
    {
        f|=(ch==‘-‘); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar(‘-‘); x=-x;
    }
    if(x<10)
    {
        putchar(x+‘0‘); return;
    }
    write(x/10);
    putchar((x%10)+‘0‘);
    return;
}
#define W(x) write(x),putchar(‘ ‘)
#define Wl(x) write(x),putchar(‘\n‘)
int Step[65536],Sta=0,End=0,Now;
queue<int>Queue;
inline void Move(int From,int To)
{
    if(Now&(1<<To)) return;
    int tmp=(Now^(1<<From))|(1<<To);
    if(~Step[tmp]) return;
    Step[tmp]=Step[Now]+1;
    Queue.push(tmp);
}
int main()
{
    memset(Step,-1,sizeof Step);
    int i,j;
    string S;
    for(i=1;i<=4;i++)
    {
        cin>>S;
        for(j=0;j<=3;j++) Sta=(Sta<<1)+(S[j]-‘0‘);
    }
    for(i=1;i<=4;i++)
    {
        cin>>S;
        for(j=0;j<=3;j++) End=(End<<1)+(S[j]-‘0‘);
    }
    Queue.push(Sta); Step[Sta]=0;
    while(!Queue.empty())
    {
        Now=Queue.front(); Queue.pop();
        if(Now==End)
        {
            return Wl(Step[Now]),0;
        }
        for(i=0;i<16;i++) if((1<<i)&Now)
        {
            if(i<12) Move(i,i+4);
            if(i>3) Move(i,i-4);
            if(i%4<3) Move(i,i+1);
            if(i%4>0) Move(i,i-1);
        }
    }
    return 0;
}
/*
input
1111
0000
1110
0010

1010
0101
1010
0101
output
4
*/