#include<bits/stdc++.h>
#define id(x,y) ((x-1)*4+y-1)//将二维转化为一维空间
#define Node bitset<16>//开个宏定义方便些
#define n 4
using namespace std;
int read() {//快速读入
int x=1,ans=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')x*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ans=ans*10+ch-48;ch=getchar();}
return x*ans;
}
int da[]={0,-1};//为避免枚举到重复情况，只往上和往左
int db[]={-1,0};//同上
bitset<65536> vis;//避免重复搜索
int main() {
Node t,s;
char tmp[10];//tmp数组下面读入要用到
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++)
s[id(i,j)]=getchar()-'0';//字符强制转化
gets(tmp);//过滤行末乱七八糟的东西
}
gets(tmp);//同上
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++)
t[id(i,j)]=getchar()-'0';//同上
gets(tmp);//同上
}
if(s==t) puts("0"),exit(0);//当前状态和预期状态相同时特判
queue<pair<Node,int> > w;//
w.push(make_pair(s,0));vis[s.to_ulong()]=true;//bitset.to_ulong()这个函数是把bitset转化为整形
while(w.size()) {//普通广搜
Node u=w.front().first;int step=w.front().second;w.pop();
for(int x=1;x<=n;x++) {
for(int y=1;y<=n;y++) {
for(int k=0;k<2;k++) {//枚举坐标和方向
int xx=x+da[k],yy=y+db[k];
if(xx<=0||xx>n||yy<=0||yy>n) continue;
if((u[id(xx,yy)]==0&&u[id(x,y)]==0)||(u[id(xx,yy)]==1&&u[id(x,y)]==1)) continue;//只有在两个位置有且只有一个1时才可以交换
bool temp=u[id(x,y)];u[id(x,y)]=u[id(xx,yy)];u[id(xx,yy)]=temp;//手动模拟交换比stl的swap函数快
if(u==t) printf("%dn",step+1),exit(0);//到达目的地输出结束
if(!vis[u.to_ulong()]) w.push(make_pair(u,step+1)),vis[u.to_ulong()]=true;//若当前状态没有入队过就push
temp=u[id(x,y)];u[id(x,y)]=u[id(xx,yy)];u[id(xx,yy)]=temp;
}
}
}
}
return 0;//这句好像在这题是废话，以防万一还是加上
} 
题解 P4289 【[HAOI2008]移动玩具】
2019-04-10 00:00:00 题解
看到没有bitset的题解，我来一发
首先安利一下我的blog http://ch66.cf/
当然在我的博客观看效果更佳
思路下面那些大佬已经讲的很清楚了，具体操作看注释
