记录编号	117509	评测结果	AAAAAAAAAA
题目名称	[HAOI 2008]移动玩具	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.111 s
提交时间	2014-08-30 11:02:10	内存使用	0.31 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>

using namespace std;

const int INF = 256;

struct node{
	int ele[4][4];
	bool operator == (const node &a)const{
		bool flag=true;
		for(int i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				if(ele[i][j]!=a.ele[i][j])
				{
					flag=false;					
				}
			}
		}
		return flag;
	}
	bool operator < (const node &a)const{
		for(int i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				if(ele[i][j]!=a.ele[i][j])
				{
					return ele[i][j] < a.ele[i][j];				
				}
			}
		}
		return 0;
	}
	bool operator != (const node &a)const{
		return !(*this==a);
	}
}a={0},b={0};

map<node,bool> G,U;
int xx[4]={1,-1,0,0};
int yy[4]={0,0,1,-1},total=0;
char ch;

void init()
{
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin>>ch;
			if(ch=='1') a.ele[i][j]=1;
			else a.ele[i][j]=0;
		}
	}
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			cin>>ch;
			if(ch=='1') b.ele[i][j]=1;
			else b.ele[i][j]=0;		
		}	
	}
}

bool pass(int x,int y)
{
	return (x>=0&&x<4)&&(y>=0&&y<4);
}

void bfs()
{
	queue<int> q;
	queue<node> p;
	p.push(a), q.push(0);
	while(!q.empty())
	{
		node o=p.front(); p.pop();
		int now=q.front(); q.pop();
		if(o==b)
		{
			cout<<now<<endl;
			return;
		}
		for(int i=0;i<4;i++)
		{
			for(int j=0;j<4;j++)
			{
				if(o.ele[i][j])
				{
					for(int k=0;k<4;k++)
					{
						if(pass(i+xx[k],j+yy[k]) && !o.ele[i+xx[k]][j+yy[k]])
						{
							swap(o.ele[i+xx[k]][j+yy[k]],o.ele[i][j]);
							if(!G[o])
							{
								p.push(o);
								q.push(now+1);
								G[o]=true;
							}
							swap(o.ele[i+xx[k]][j+yy[k]],o.ele[i][j]);
						}
					}
				}
			}
		}
	}
}

int main()
{
	freopen("movea.in","r",stdin);
	freopen("movea.out","w",stdout);
	
	init();
	bfs();	
	
	return 0;
}

/*
1111
0000
1110
0010

1010
0101
1010
0101
*/