#include<iostream>
#include<math.h>
using namespace std;
int source,dest=87654321;
int ten[10],jie[10],order[9][9];
const int C[]={2,3,2,3,4,3,2,3,2};
const int CC[][4]={{1,3,-1},{0,2,4},{1,5,-1},{0,6,4},{1,3,5,7},{2,4,8,-1},{3,7},{4,6,8},{5,7}};
const char DIR[][4]={{'r','d',-1},{'l','r','d'},{'l','d',-1}
					 ,{'u','d','r'},{'u','l','r','d'},{'u','l','d',-1}
					 ,{'u','r'},{'u','l','r'},{'u','l'}};


struct NODE
{
	int data;
	int parent;
	int step;
	char dir;
};
int   visit[362880]={0};
int   parr[362880]={0};
NODE arr1[362880/2],arr2[362880/2];					 
int  head1=0,tail1=0,head2=0,tail2=0;
int step1=0,step2=0,step;
char oppo(char ch)
{
	char re;
	if(ch=='l')
		re='r';
	if(ch=='r')
		re='l';
	if(ch=='u')
		re='d';
	if(ch=='d')
		re='u';
return re;	
}
int hash(int num)
{
	int tmp[9],i=0,j=0;
	int count=0;
	for(i=0;i<9;i++)
	{
		tmp[i]=(num/ten[i])%10;
	}
	for(i=0;i<9;i++)
		for(j=i+1;j<9;j++)
	{

		if(tmp[j]>tmp[i])
			count+=jie[8-i];
	}
	return count;
}
int exchange(int num,int i,int j)//i位和j位交换
{
	int numi=(num/ten[i])%10;
	int numj=(num/ten[j])%10;

	num+=numj*ten[i]+numi*ten[j]-numj*ten[j]-numi*ten[i];
	return num;
}
void read(int &num)
{

	char tmp;
	int i=0;	
//	FILE *pf=fopen(file,"r");
//	FILE *pf=stdin;
	num=0;
	while(scanf("%c",&tmp)!=EOF)
	{
		if(tmp>'0' && tmp<'9')
			num+=(tmp-'0')*ten[i++];	
		if(tmp=='0' || tmp=='x' || tmp=='X')
			i++;
	}
}
int rev(int num)
{
	int tmp[9],i=0,j=0;
	int count=0;
	for(i=0;i<9;i++)
	{
		tmp[i]=(num/ten[i])%10;
	}
	for(i=0;i<9;i++)
		for(j=i+1;j<9;j++)
	{

		if(tmp[i]!=0 && tmp[j]!=0 && tmp[j]<tmp[i])
			count++;
	}
	return count;
}
bool issov()
{
	int a=rev(dest);
	int b=rev(source);
	int even=abs(rev(source)-rev(dest));
	if(even&1)
		return false;
	return true;
}
void printway(int index1,int index2)
{
	char way[100];
	int pway=0;
	int tmp=index1;
	int i;


//	cout<<step<<endl;
	while(tmp!=-1)
	{
		way[pway++]=arr1[tmp].dir;
		tmp=arr1[tmp].parent;
	}
	pway--;
	for(i=pway-1;i>=0;i--)
		cout<<way[i];

	pway=0;
	tmp=index2;
	while(tmp!=-1)
	{
		//way[pway++]=arr1[tmp].dir;
		if(arr2[tmp].dir)
			cout<<oppo(arr2[tmp].dir);
		tmp=arr2[tmp].parent;
	}



}
bool search1()//一次前进一层
{
	int tptail=tail1;
	step1++;
	for(int i=head1;i<=tptail;i++)
	{
		int b=0;
		int current=arr1[i].data;
		for(b=0;(current/ten[b])%10;b++);
		for(int j=0;j<C[b];j++)
		{
			int newnode=exchange(current,b,CC[b][j]);
			int index=hash(newnode);

			++tail1;
			arr1[tail1].data=newnode;
			arr1[tail1].dir=DIR[b][j];
			arr1[tail1].parent=i;
			arr1[tail1].step=step1;

			if(visit[index]==0)
			{
				visit[index]=1;
				parr[index]=tail2;
			}else if(visit[index]<0)//search2访问过了
			{
				step=step1+arr2[parr[index]].step;
				printway(tail1,parr[index]);
				return true;
			}else
				tail1--;

		}
	}
	head1=tptail+1;
	return false;
}
bool search2()
{
	int tptail=tail2;
	step2++;
	for(int i=head2;i<=tptail;i++)
	{
		int b=0;
		int current=arr2[i].data;
		for(b=0;(current/ten[b])%10;b++);
		for(int j=0;j<C[b];j++)
		{
			int	newnode=exchange(current,b,CC[b][j]);
			int index=hash(newnode);
			++tail2;
			arr2[tail2].data=newnode;
			arr2[tail2].dir=DIR[b][j];
			arr2[tail2].parent=i;
			arr2[tail2].step=step2;
			

			if(visit[index]==0)
			{
				visit[index]=-1;
				parr[index]=tail2;
			}else if(visit[index]>0)//search1访问过了
			{
				step=arr1[parr[index]].step+step2;
				printway(parr[index],tail2);
				return true;
			}else
				tail2--;

		}
	}
	head2=tptail+1;
	return false;
}
void solve()
{

	head1=tail1=0;
	step1=step2=0;
	arr1[0].data=source;
	arr1[0].dir=0;
	arr1[0].parent=-1;
	arr1[0].step=0;

	head2=tail2=0;
	arr2[0].data=dest;
	arr2[0].dir=0;
	arr2[0].parent=-1;
	arr2[0].step=0;


	visit[hash(source)]=1;
	visit[hash(dest)]=-1;
	parr[hash(source)]=0;
	parr[hash(dest)]=0;

	while(true)
	{
			if(search1())
				break;
			if(search2())
				break;
	}
}
int main()
{	
//	freopen("out.txt","w",stdout);
//	freopen("start.txt","r",stdin);
	int i=0;
	ten[0]=1;
	for(i=1;i<10;i++)
		ten[i]=10*ten[i-1];
	jie[0]=1;
	for(i=1;i<10;i++)
		jie[i]=i*jie[i-1];

	read(source);
	if(issov())
	{
		if(source!=dest)
			solve();
	}else
	{
		printf("unsolvable");
	}
	return 1;
}

• Re:求救WA?? (105) wenchao 2009-05-16 00:52:45