[BZOJ1054][HAOI2008]移动玩具 bfs+hash

2022-11-06 09:05:05

1054: [HAOI2008]移动玩具

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2432 Solved: 1355
[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

bfs+hash

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 char a[][];

 int t=;

 int k=;

 int now=;

 int dis[];

 int q[];

 void bfs() {

     memset(dis,,sizeof(dis));

     int head=,tail=;

     q[head]=now;

     dis[now]=;

     while(head!=tail) {

         int n=q[head++];

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

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

                 int to=<<((i-)*+j-);

                 if(!(n&to)) continue;

                 if(i>) {

                     int tt=to>>;

                     if(!(n&tt)) {

                         int next=n-to+tt;

                         if(dis[next]>dis[n]+) {dis[next]=dis[n]+;q[tail++]=next;}

                         if(next==t){printf("%d",dis[next]);return;}

                     }

                 }

                 if(j>) {

                     int tt=to>>;

                     if(!(n&tt)) {

                         int next=n-to+tt;

                         if(dis[next]>dis[n]+) {dis[next]=dis[n]+;q[tail++]=next;}

                         if(next==t){printf("%d",dis[next]);return;}

                     }

                 }

                 if(j<) {

                     int tt=to<<;

                     if(!(n&tt)) {

                         int next=n-to+tt;

                         if(dis[next]>dis[n]+) {dis[next]=dis[n]+;q[tail++]=next;}

                         if(next==t){printf("%d",dis[next]);return;}

                     }

                 }

                 if(i<) {

                     int tt=to<<;

                     if(!(n&tt)) {

                         int next=n-to+tt;

                         if(dis[next]>dis[n]+) {dis[next]=dis[n]+;q[tail++]=next;}

                         if(next==t){printf("%d",dis[next]);return;}

                     }

                 }

              }

         }

     }

 }

 int main(){

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

         scanf("%s",a[i]);

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

             now+=(a[i][j-]-'')*k;

             k<<=;

         }

     }

     k=;

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

         char x[];

         scanf("%s",x);

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

             t+=(x[j-]-'')*k;

             k<<=;

         }

     }

     bfs();

 }

码农公寓