hdu 1043 Eight 搜索，哈希

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=1000008;
int md[12];
void init()
{
	int i,j;
	md[0]=1;
	for(i=1;i<=8;i++)
	{
		int ans=1;
		for(j=1;j<=i;j++)
			ans*=j;
		md[i]=ans;
	}
}
int cator(int a[],int n)
{
	int i,j,k;
	int ans=0;
	for(i=1;i<=n;i++)
	{
		k=0;
		for(j=i+1;j<=n;j++)
			if(a[i]>a[j])
				k++;
		ans+=k*md[n-i];
	}
	return ans;
}
void fuckcator(int ha,int n,int a[])
{
	int i,j,t;
	bool vis[11];
	memset(vis,false,sizeof(vis));
	for(i=1;i<=n;i++)
	{
		t=ha/md[n-i];
		for(j=1;j<=n;j++)
			if(!vis[j])
			{
				if(t==0)	break;
				--t;
			}
		a[i]=j;
		vis[j]=true;
		ha%=md[n-i];
	}
}
int pre[maxn];
char shit[maxn];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
char d[5]={‘u‘,‘l‘,‘d‘,‘r‘};
bool judge(int x)
{
	if(x>=0&&x<3)
		return true;
	return false;
}
void bfs()
{
	queue<int>	q;
	int a[11],i;
	for(i=1;i<=8;i++)	a[i]=i;a[9]=0;
	int ha=cator(a,9);
	int nha,x,y,nx,ny,pos,npos;
	q.push(ha);pre[ha]=ha;shit[ha]=‘\n‘;
	while(!q.empty())
	{
		ha=q.front();q.pop();
		fuckcator(ha,9,a);
		for(i=1;i<=9;i++)	if(a[i]==1)	pos=i-1;
		y=pos%3;x=pos/3;
		for(i=0;i<4;i++)
		{
			nx=x+dir[i][0];
			ny=y+dir[i][1];
			if(judge(nx)&&judge(ny))
			{
				npos=nx*3+ny;
				swap(a[pos+1],a[npos+1]);
				nha=cator(a,9);
				swap(a[pos+1],a[npos+1]);
				if(pre[nha]!=-1)	continue;
				q.push(nha);
				pre[nha]=ha;
				shit[nha]=d[i];
			}
		}
	}
}
int main()
{
	int i,j,k,n,ha;
	int a[11],b[11];
	char s[100];
	init();
	memset(pre,-1,sizeof(pre));
	bfs();
	while(gets(s))
	{
		int j=1;
		for(i=0;s[i]!=‘\0‘;i++)
		{
			if(s[i]>=‘1‘&&s[i]<=‘8‘)
				a[j++]=s[i]-‘0‘;
			else	if(s[i]==‘x‘)
				a[j++]=0;
		}
		ha=cator(a,9);
		if(pre[ha]==ha)	printf("lr\n");
		else if(pre[ha]==-1)	printf("unsolvable\n");
		else
		{
			for(i=ha;i!=pre[i];i=pre[i])printf("%c",shit[i]);
			printf("\n");
		}
	}
	return 0;
}