#include <stdio.h>
#include <string.h>
long jc[10]={1,1,2,6,24,120,720,5040,40320,362880};
int a[400000][12];
int a1[12];
int si[400000],ans[40];
long i,j,k,n,head,tip,temp,zk,tot,signsign=0;
long zhankai()
{
	int i,j,temp,n=9,t=0;
	for (i=0;i<n;i++)
	{
		temp=0;
		for (j=i+1;j<n;j++)
			if (a1[j]<a1[i]) temp++;
		t+=temp*jc[n-i-1];
	}
	return t;
}
main()
{
	char h;
	memset(a,0,sizeof(a));
	memset(a1,0,sizeof(a1));
	memset(si,0,sizeof(si));
	for (i=0;i<9;i++)
	{
		scanf("%s",&h);
		if (h=='x') {a[1][i]=0;a[1][9]=i;}
			else a[1][i]=h-48;
	}

	head=1;
	tip=1;

	while (head<=tip)
	{
		for (i=0;i<12;i++)
			a1[i]=a[head][i];
		
		zk=zhankai();
		if (zk==46233) 
		{
			k=head;
			tot=0;
			while (k!=0)
			{
				tot++;
				ans[tot]=a[k][11];
				k=a[k][10];
			}
			while (tot!=0)
			{
				switch (ans[tot])
				{
					case 1:printf("u");break;
					case 2:printf("l");break;
					case 3:printf("r");break;
					case 4:printf("d");break;
					default:break;
				}
				tot--;
			}
			signsign=1;
			break;
		}


		si[zk]=1;
		head++;
		
		k=a1[9];
		if (k>=3)
		{
			temp=a1[k];a1[k]=a1[k-3];a1[k-3]=temp;
			zk=zhankai();
			if (si[zk]==0)
			{
				tip++;
				for (i=0;i<9;i++)	a[tip][i]=a1[i];
				a[tip][9]=k-3;
				a[tip][10]=head-1;
				a[tip][11]=1;
				si[zk]=1;
			}
			temp=a1[k];a1[k]=a1[k-3];a1[k-3]=temp;
		}
		

		if (k%3!=0)
		{
			temp=a1[k];a1[k]=a1[k-1];a1[k-1]=temp;
			zk=zhankai();
			if (si[zk]==0)
			{
				tip++;
				for (i=0;i<9;i++)	a[tip][i]=a1[i];
				a[tip][9]=k-1;
				a[tip][10]=head-1;
				a[tip][11]=2;
				si[zk]=1;
			}
			temp=a1[k];a1[k]=a1[k-1];a1[k-1]=temp;
		}

		if (k%3!=2)
		{
			temp=a1[k];a1[k]=a1[k+1];a1[k+1]=temp;
			zk=zhankai();
			if (si[zk]==0)
			{
				tip++;
				for (i=0;i<9;i++)	a[tip][i]=a1[i];
				a[tip][9]=k+1;
				a[tip][10]=head-1;
				a[tip][11]=3;
				si[zk]=1;
			}
			temp=a1[k];a1[k]=a1[k+1];a1[k+1]=temp;
		}

		if (k<6)
		{
			temp=a1[k];a1[k]=a1[k+3];a1[k+3]=temp;
			zk=zhankai();
			if (si[zk]==0)
			{
				tip++;
				for (i=0;i<9;i++)	a[tip][i]=a1[i];
				a[tip][9]=k+3;
				a[tip][10]=head-1;
				a[tip][11]=4;
				si[zk]=1;
			}
			temp=a1[k];a1[k]=a1[k+3];a1[k+3]=temp;
		}


	
	}
	if (signsign==0) printf("unsolvable");

}

• 写了个A* 63ms了 (0) infoG 2013-09-07 17:41:01