bzoj1054 [HAOI2008]移动玩具-白红宇

bzoj1054 [HAOI2008]移动玩具

阅读量：5147 次

发布时间：2019-06-13

本文共 1887 字，大约阅读时间需要 6 分钟。

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec Memory Limit: 162 MB

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

HINT

Source

Tips：

　　因为这个4*4的矩阵最多只有 2^16 种状态，我们可以暴力BFS，用hash表去重就行了；

Code：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         using namespace std;int n,m,a[5][5],ans[5][5],st,ed,b[5][5];int hash,hashans,que[100008],dis[100008];char ch;map
          
           q;void solve(int u){ for(int i=1;i<=4;i++) for(int j=1;j<=4;j++){ b[i][j]=u%2; u=u/2; }}int calc(){ int res=0,k=1; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++){ res=res+k*b[i][j]; k<<=1; } return res;}int main(){ int k=1; for(int i=1;i<=4;i++){ for(int j=1;j<=4;j++){ scanf("%c",&ch); a[i][j]=ch-48; hash=hash+k*a[i][j]; k<<=1; } getchar(); } k=1; getchar(); for(int i=1;i<=4;i++){ for(int j=1;j<=4;j++){ scanf("%c",&ch); ans[i][j]=ch-48; hashans=hashans+k*ans[i][j]; k<<=1; } getchar(); } if(hash==hashans){ printf("0\n"); return 0; } q[hash]=1; que[1]=hash; dis[1]=0; st=0; ed=1; while(st
           
            0&&!b[i-1][j]){ b[i-1][j]=1; hash=calc(); if(hash==hashans){ printf("%d",y+1); return 0; } if(q[hash]==0){ q[hash]=1; ed++; que[ed]=hash; dis[ed]=y+1; } b[i-1][j]=0; } if((j+1)<=4&&!b[i][j+1]){ b[i][j+1]=1; hash=calc(); if(hash==hashans){ printf("%d",y+1); return 0; } if(q[hash]==0){ q[hash]=1; ed++; que[ed]=hash; dis[ed]=y+1; } b[i][j+1]=0; } if((j-1)>0&&!b[i][j-1]){ b[i][j-1]=1; hash=calc(); if(hash==hashans){ printf("%d",y+1); return 0; } if(q[hash]==0){ q[hash]=1; ed++; que[ed]=hash; dis[ed]=y+1; } b[i][j-1]=0; } b[i][j]=1; } } }