sxczf's Blog

在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。

一个整数，所需要的最少移动次数。

/**************************************************************
    Problem: 1054
    User: sxczf
    Language: C++
    Result: Accepted
    Time:36 ms
    Memory:1976 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
using namespace std;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
int a,b,c,de,e,f,g,h,i,j,k,l,m,n,s[5],r,now,now2,dis[100005],dl[100005],vis[100005];
char ss[10];
void add(int x){
    c=0;
    c=s[1]*4096+s[2]*256+s[3]*16+s[4];
    if (!vis[c]&&dis[c]>x){
        dis[c]=x;
        vis[c]=1;
        dl[++r]=c;
    }
}
void bfs(){
    memset(dis,0x7f,sizeof(dis));
    l=1;r=1;dl[1]=a;dis[a]=0;vis[a]=1;
    while (l<=r){
        now=dl[l];now2=dl[l];
        s[4]=now%16;
        now/=16;
        s[3]=now%16;
        now/=16;
        s[2]=now%16;
        now/=16;
        s[1]=now%16;
        now/=16;
        for(i=1;i<=4;i++){
            for(j=1;j<=4;j++)
            if (s[i]&(1<<(j-1))){s[i]^=1<<(j-1);
                if (i>1&&!(s[i-1]&(1<<(j-1)))){s[i-1]^=(1<<(j-1));add(dis[now2]+1);s[i-1]^=(1<<(j-1));}
                if (i<4&&!(s[i+1]&(1<<(j-1)))){s[i+1]^=(1<<(j-1));add(dis[now2]+1);s[i+1]^=(1<<(j-1));}
                if (j>1&&!(s[i]&(1<<(j-2)))){s[i]^=(1<<(j-2));add(dis[now2]+1);s[i]^=(1<<(j-2));}
                if (j<4&&!(s[i]&(1<<(j)))){s[i]^=(1<<(j));add(dis[now2]+1);s[i]^=(1<<(j));}
                s[i]^=1<<(j-1);
            }
        }
        l++;
    }
}
int main(){
    for(i=1;i<=4;i++){
        scanf("%s",ss);
        for(j=0;j<=3;j++)
        a=a*2+ss[j]-'0';
    }
    for(i=1;i<=4;i++){
        scanf("%s",ss);
        for(j=0;j<=3;j++)
        b=b*2+ss[j]-'0';
    }
    bfs();
    printf("%d",dis[b]);
    return 0;
}