先贴一波题面
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
00101010
0101
1010
0101Sample Output
4
这题乍一看感觉怪怪的，后来一看数据规模固定为16位，状压DP可过
我所选择的策略是BFS，从开始状态枚举可能的转移状态，更新状态并入队
袋马如下：
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> int dp[<<];
int origin;
int goal;
bool inQueue[<<]; void Initialize();
void BFS(int); int main(){
Initialize();
BFS(origin);
printf("%d\n",dp[goal]);
return ;
} void BFS(int origin){
int top,target;
std::queue<int> q;
q.push(origin);
dp[origin]=;
while(!q.empty()){
top=q.front();
q.pop();
for(int i=;i<;i++){
if((top&(<<i))==)
continue;
if(i>=&&(top&(<<(i-)))==){
target=(top^(<<i))^(<<(i-));
if(dp[target]>dp[top]+){
dp[target]=dp[top]+;
if(!inQueue[target]){
q.push(target);
inQueue[target]=true;
}
}
}
if(i<=&&(top&(<<(i+)))==){
target=(top^(<<i))^(<<(i+));
if(dp[target]>dp[top]+){
dp[target]=dp[top]+;
if(!inQueue[target]){
q.push(target);
inQueue[target]=true;
}
}
}
if(i%>&&(top&(<<(i-)))==){
target=(top^(<<i))^(<<(i-));
if(dp[target]>dp[top]+){
dp[target]=dp[top]+;
if(!inQueue[target]){
q.push(target);
inQueue[target]=true;
}
}
}
if(i%<&&(top&(<<(i+)))==){
target=(top^(<<i))^(<<(i+));
if(dp[target]>dp[top]+){
dp[target]=dp[top]+;
if(!inQueue[target]){
q.push(target);
inQueue[target]=true;
}
}
}
}
}
} void Initialize(){
freopen("movea.in","r",stdin);
freopen("movea.out","w",stdout);
int pos=;
char ch=getchar();
while(pos>=){
while(!isdigit(ch))
ch=getchar();
origin^=(ch-'')<<pos;
--pos;
ch=getchar();
}
pos=;
while(pos>=){
while(!isdigit(ch))
ch=getchar();
goal^=(ch-'')<<pos;
--pos;
ch=getchar();
}
memset(dp,0x7F,sizeof(dp));
// printf("%X %X\n",origin,goal);
}
Backup
然后是图包时间