首页 > 代码库 > [HAOI 2005][BZOJ 1054] 移动玩具
[HAOI 2005][BZOJ 1054] 移动玩具
先贴一波题面
1054: [HAOI2008]移动玩具
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2288 Solved: 1270Description
在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。Input
前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。Output
一个整数,所需要的最少移动次数。
Sample Input
1111
0000
1110
0010
1010
0101
1010
0101Sample Output
4
这题乍一看感觉怪怪的,后来一看数据规模固定为16位,状压DP可过
我所选择的策略是BFS,从开始状态枚举可能的转移状态,更新状态并入队
袋马如下:
GitHub
1 #include <queue> 2 #include <cstdio> 3 #include <cctype> 4 #include <cstring> 5 #include <cstdlib> 6 #include <iostream> 7 #include <algorithm> 8 9 int dp[1<<16]; 10 int origin; 11 int goal; 12 bool inQueue[1<<16]; 13 14 void Initialize(); 15 void BFS(int); 16 17 int main(){ 18 Initialize(); 19 BFS(origin); 20 printf("%d\n",dp[goal]); 21 return 0; 22 } 23 24 void BFS(int origin){ 25 int top,target; 26 std::queue<int> q; 27 q.push(origin); 28 dp[origin]=0; 29 while(!q.empty()){ 30 top=q.front(); 31 q.pop(); 32 for(int i=0;i<16;i++){ 33 if((top&(1<<i))==0) 34 continue; 35 if(i>=4&&(top&(1<<(i-4)))==0){ 36 target=(top^(1<<i))^(1<<(i-4)); 37 if(dp[target]>dp[top]+1){ 38 dp[target]=dp[top]+1; 39 if(!inQueue[target]){ 40 q.push(target); 41 inQueue[target]=true; 42 } 43 } 44 } 45 if(i<=11&&(top&(1<<(i+4)))==0){ 46 target=(top^(1<<i))^(1<<(i+4)); 47 if(dp[target]>dp[top]+1){ 48 dp[target]=dp[top]+1; 49 if(!inQueue[target]){ 50 q.push(target); 51 inQueue[target]=true; 52 } 53 } 54 } 55 if(i%4>0&&(top&(1<<(i-1)))==0){ 56 target=(top^(1<<i))^(1<<(i-1)); 57 if(dp[target]>dp[top]+1){ 58 dp[target]=dp[top]+1; 59 if(!inQueue[target]){ 60 q.push(target); 61 inQueue[target]=true; 62 } 63 } 64 } 65 if(i%4<3&&(top&(1<<(i+1)))==0){ 66 target=(top^(1<<i))^(1<<(i+1)); 67 if(dp[target]>dp[top]+1){ 68 dp[target]=dp[top]+1; 69 if(!inQueue[target]){ 70 q.push(target); 71 inQueue[target]=true; 72 } 73 } 74 } 75 } 76 } 77 } 78 79 void Initialize(){ 80 freopen("movea.in","r",stdin); 81 freopen("movea.out","w",stdout); 82 int pos=15; 83 char ch=getchar(); 84 while(pos>=0){ 85 while(!isdigit(ch)) 86 ch=getchar(); 87 origin^=(ch-‘0‘)<<pos; 88 --pos; 89 ch=getchar(); 90 } 91 pos=15; 92 while(pos>=0){ 93 while(!isdigit(ch)) 94 ch=getchar(); 95 goal^=(ch-‘0‘)<<pos; 96 --pos; 97 ch=getchar(); 98 } 99 memset(dp,0x7F,sizeof(dp)); 100 // printf("%X %X\n",origin,goal); 101 }
然后是图包时间
[HAOI 2005][BZOJ 1054] 移动玩具
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。