「BZOJ1054」[HAOI2008] 移动玩具
Description
在一个4*4的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。
Input
前4行表示玩具的初始状态，每行4个数字1或0，1表示方格中放置了玩具，0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态，每行4个数字1或0，意义同上。
Output
一个整数，所需要的最少移动次数。
Sample Input
1111
0000
1110
0010
0000
1110
0010
1010
0101
1010
0101
Sample Output
4
题解
md。。广搜。。传说中不用判重也能过！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int bg,ed,h,xx[4]={0,0,1,-1},yy[4]={1,-1,0,0}; bool ans[5][5],mark[65536]; struct data{bool a[5][5];int step;}q[65536]; int hash(bool a[5][5]) { int k=1,s=0; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) {s+=k*a[i][j];k<<=1;} return s; } void bfs() { int t=0,w=1; char ch[5]; for(int i=1;i<=4;i++) { scanf("%s",ch); for(int j=1;j<=4;j++) q[0].a[i][j]=ch[j-1]-'0'; } for(int i=1;i<=4;i++) { scanf("%s",ch); for(int j=1;j<=4;j++) ans[i][j]=ch[j-1]-'0'; } bg=hash(q[t].a); ed=hash(ans); if(bg==ed){printf("0");return;} mark[bg]=1; int x,y; while(t<w) { for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) if(q[t].a[i][j]) for(int k=0;k<4;k++) { x=i+xx[k],y=j+yy[k]; if(q[t].a[x][y]||x>4||y>4||x<1||y<1)continue; swap(q[t].a[i][j],q[t].a[x][y]); h=hash(q[t].a); if(!mark[h]){ if(h==ed){printf("%d",q[t].step+1);return;} mark[h]=1; memcpy(q[w].a,q[t].a,sizeof(q[w].a)); q[w].step=q[t].step+1; w++; } swap(q[t].a[i][j],q[t].a[x][y]); } t++; } } int main() { bfs(); return 0; } |
Subscribe
计数器 9774584
OI 课件=>
OI 课件=>