嗯~很久以前没敲过的题，当时不懂状态压缩，不懂A*。因而没过...
现在用的康托展开+普通的BFS还是过了360ms也算是一个进步吧~
A*现在还是没有勇气去写... 加油！时间给我的不多了！~
（用C++TLE了... 改为G++就过了...）
Code：
#include<stdio.h>
#include<queue>
using namespace std;struct node
{int eight[9];
}S,E;
int fec[10]={1,1,2,6,24,120,720,5040,40320,362880 };void init()
{char s;int i=0;while( scanf("%c",&s)!=EOF ){if( s!=' ' ){if( s=='x' )S.eight[i++]=9;elseS.eight[i++]=s-'0';}}for( i=0;i<9;i++ )E.eight[i]=i+1;
}int nodeToNum( node a )
{int ret=0;for( int i=0;i<9;i++ )ret=ret*10+a.eight[i];return ret;
}int cantor( node a )
{int ret=0;bool flag[10]={false};for( int i=0;i<9;i++ ){int k=a.eight[i];flag[k]=true;int p=0;for( int j=1;j<k;j++ )if( flag[j]==false )p++;ret+=p*fec[8-i];}return ret;
}char select[400000];
char item[5]={ ' ','u','r','d','l' };
int pre[400000];
bool hash[400000]={false};void swap( int &a,int &b )
{a=a^b;b=a^b;a=a^b;
}node work( node a,int n )
{int index;for( int i=0;i<9;i++ )if( a.eight[i]==9 )index=i;if( n==1 ){if( index-3>=0 )swap( a.eight[index],a.eight[index-3] );}else if( n==2 ){if( index%3!=2 )swap( a.eight[index],a.eight[index+1] );}else if( n==3 ){if( index+3<9 )swap( a.eight[index],a.eight[index+3] ); }else if( n==4 ){if( index%3!=0 )swap( a.eight[index],a.eight[index-1] );}return a;
}void print( int at )
{char cans[40000];int len=0;for( int i=at;pre[i]!=-1;i=pre[i] )cans[len++]=select[i];for( int i=len-1;i>=0;i-- )printf( "%c",cans[i] );printf( "\n" );
}void bfs()
{queue<node> Q;Q.push(S);int head=0;int foot=1;pre[0]=-1;hash[cantor(S)]=true;if( nodeToNum(S)==nodeToNum(E) ){ printf( "\n" );return ;}while( !Q.empty() ){node cur=Q.front();Q.pop();node temp;for( int i=1;i<=4;i++ ){temp=work( cur,i );int ans=cantor(temp);if( hash[ans]==false ){hash[ans]=true;pre[foot]=head;select[foot]=item[i];foot++;Q.push(temp);if( nodeToNum(temp)==nodeToNum(E) ){print( foot-1 );return ;}}}head++;}printf( "unsolvable\n" );
}int main()
{freopen( "poj 1077.in","r",stdin );freopen( "poj 1077.out","w",stdout );init();bfs();return 0;
}