[POJ2965]The Pilots Brothers’ refrigerator[BFS,位运算]

#include<cstdio>
#include<queue>
#define re register
#define in inline
using namespace std;
in int read()
{
	int s(0),b(0);char ch;
	do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	if(b) return -s;
	return s;
}
struct node{int v,step;};
queue<node> q;
int b[130000],pre[130000][2];//pre[sta][0]表示状态sta的前驱状态(由于不会重复搜索一个状态,所以每个状态的前驱唯一), [1]存放此步操作的坐标.
in void cg(int &t,int h,int l)
{
	for(re int j=1;j<=4;++j)
		t=t^(1<<((h-1)*4+j-1));
	for(re int i=1;i<=4;++i)
		t=t^(1<<((i-1)*4+l-1));
	t=t^(1<<((h-1)*4+l-1));
}//对(h,l)进行操作
in int bfs()
{
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		for(re int i=1;i<=4;++i)
		{
			for(re int j=1;j<=4;++j)
			{
				node t=now;
				cg(t.v,i,j);
				if(b[t.v]) continue;
				pre[t.v][0]=now.v,pre[t.v][1]=(i-1)*4+j;//记录路径
				if(t.v==0) return t.step+1;
				b[t.v]=1,++t.step;
				q.push(t);
			}
		}
	}
}
in void out(int sta)
{
	if(pre[sta][0]!=-1) out(pre[sta][0]);
	else return;
	printf("%d %d\n",(pre[sta][1]-1)/4+1,(pre[sta][1]-1)%4+1);
}
signed main()
{
	int st=0;
	char str[5];
	for(re int i=1;i<=4;++i)
	{
		scanf("%s",str);
		for(re int j=0;j<4;++j)
			if(str[j]=='+') st=st|(1<<((i-1)*4+j));
	}
	if(!st){printf("0\n");return 0;}
	b[st]=1;
	pre[st][0]=-1;
	node t;
	t.v=st,t.step=0;
	q.push(t);
	printf("%d\n",bfs());
	out(0);
	return 0;
}