[BZOJ1054] 移动玩具

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2741 Solved: 1537
[Submit][Status][Discuss]

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

提交地址 ： BZOJ1054

题解：

调了很久，我还是太菜了；

就是广搜，没什么难度；

一个数组写错了调了半天QAQ；

Code:

 #include <iostream>

 #include <cstdio>

 #include <queue>

 #include <cstring>

 using namespace std;

 int dx[]={, , , -, }, dy[]={, , , , -};

 bool a[][], b[][];

 inline int Hash(bool t[][])

 {

     int k = , s = ;

     for (register int i =  ; i <=  ; i ++)

     {

         for (register int j =  ; j <=  ;j ++)

         {

             s += k * t[i][j];k <<= ;

         }

     }

     return s;

 }

 bool vis[];

 struct date

 {

     bool o[][];

     int stp;

 }q[];

 int main()

 {

     for (register int i =  ; i <=  ; i ++)

         for (register int j =  ; j <=  ; j ++)

             scanf("%1d", &a[i][j]), q[].o[i][j] = a[i][j];

     for (register int i =  ; i <=  ; i ++)

         for (register int j =  ; j <=  ; j ++)

             scanf("%1d", &b[i][j]);

     int beg = Hash(a), end = Hash(b);

     if (beg == end) {puts("");return ;}

     vis[beg] = ;

     int l = , r = ;

     while (l < r)

     {

         for (register int i =  ; i <=  ; i ++)

         {

             for (register int j =  ; j <=  ; j ++)

             {

                 if (!q[l].o[i][j]) continue;

                 for (register int k =  ; k <=  ; k ++)

                 {

                     int x = i + dx[k], y = j + dy[k];

                     if (q[l].o[x][y]) continue;

                     if (x <=  or y <=  or x >  or y > ) continue;

                     swap(q[l].o[i][j], q[l].o[x][y]);

                     int H = Hash(q[l].o);

                     if (!vis[H])

                     {

                         if (H == end) {printf("%d\n", q[l].stp +);return ;}

                         vis[H] = ;

                         memcpy(q[r].o, q[l].o, sizeof q[r].o);

                         q[r].stp = q[l].stp + ;

                         r++;

                     }

                     swap(q[l].o[i][j], q[l].o[x][y]);

                 }

             }

         }

         l++;

     }

     return ;

 }

巴特西