Description

　　在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动

时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移

动到某人心中的目标状态。

Input

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

行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。

Output

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

Sample Input

1111

0000

1110

0010

1010

0101

1010

0101

Sample Output

4

搜索，求最优的就用BFS，记得判重复状态就好

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 char a[6][6],b[6][6]; 7 struct node{ 8     char a[6][6]; 9 }A,B,T,q[1000001];10 int Ans[1000001],dx[5]={
   0,1,-1,0,0},dy[5]={
   0,0,0,1,-1};11 bool f[1000001];12 int judge(node A)13 {14     int ans=0,base=1;;15     for (int i=1;i<=4;++i)16         for (int j=1;j<=4;++j)17             ans+=base*(A.a[i][j]-48),base*=2;18     return ans;19             20 }21 int main()22 {23     char ch[10];24     memset(A.a,-1,sizeof(a));25     memset(B.a,-1,sizeof(b));26     for (int i=1;i<=4;++i)27     {28         scanf("%s",ch);29         for (int j=1;j<=4;++j)30             A.a[i][j]=ch[j-1];31     }32     for (int i=1;i<=4;++i)33     {34         scanf("%s",ch);35         for (int j=1;j<=4;++j)36             B.a[i][j]=ch[j-1];37     }38     int head=0;39     int tail=1;40     q[1]=A;41     f[judge(A)]=true;42     if (judge(A)==judge(B))43     {44         printf("0");45         return 0;46     }47     do48     {49         ++head;50         node T=q[head];51         for (int i=1;i<=4;++i)52             for (int j=1;j<=4;++j)53                 if (T.a[i][j]=='1')54                     for (int k=1;k<=4;++k)55                         if (T.a[i+dx[k]][j+dy[k]]=='0')56                         {57                             swap(T.a[i][j],T.a[i+dx[k]][j+dy[k]]);58                             int x=judge(T);59                             if (!f[x])60                             {                                    61                                 ++tail;62                                 q[tail]=T;63                                 f[x]=true;64                                 Ans[tail]=Ans[head]+1;65                                 if (x==judge(B))66                                 {67                                     printf("%d",Ans[tail]);68                                     return 0;69                                 }                            70                             }71                             swap(T.a[i][j],T.a[i+dx[k]][j+dy[k]]);72                         }73     }while (head