#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 5
int sd,key=0;
int vis[1<<16];
int dir[16] = {4383,8751,17487,34959,4593,8946,17652,35064,7953,12066,
20292,36744,61713,61986,62532,63624};
struct node
{
	int sum,num,step;
}cur;
struct path
{
	int x,pre;
}p[100001];
void f(int index)
{
	if(index)
	{
		f(p[index].pre);
		printf("%d %d\n",p[index].x/4+1,p[index].x%4+1);
	}
}
void bfs()
{
	int i,j,k;
	cur.sum=sd;
	cur.num=0;
	cur.step=0;
	p[1].pre=0;
	queue<node>q;
	q.push(cur);
	while(!q.empty())
	{
		node b=q.front();
		q.pop();
		if(b.sum==0)
		{
			printf("%d\n",b.step);
			f(b.num);
			return;
		}
		for(i=0;i<16;i++)
		{
			node a=b;
			a.sum^=dir[i];
			if(!vis[a.sum])
			{
				a.num=++key;
				a.step++;
				p[key].pre=b.num;
				p[key].x=i;
				q.push(a);
				vis[a.sum]=1;
			}
		}
	}
}
int main()
{
	int i,j;
	char s[5];
	for(i=0;i<4;i++)
	{
		scanf("%s",s);
		for(j=0;j<4;j++)
		{
			if(s[j]=='+')
			{
				sd+=(1<<i*4+j);
			}			
		}
	}
	bfs();
	return 0;
}

• Re:BFS+位运算+回溯路径，G++500MS (1265) w343051232 2012-10-26 13:03:45
• Re:BFS+位运算+回溯路径，G++500MS (1271) 894212550 2013-11-18 22:57:12