我先从目的态扩展到各种状态，然后记录，每问一个，我就哈希到对应状，然后向上走到树根输出，如果哈希到对应的状态是没有出现过的，则是unsolvable。提交WA，请问这样做有什么错误？一般数据我写了测试程序测过，没问题。。



/*
 Wrong Answer  	1217  	C++  	260  	5360  	wolf
*/
#pragma warning ( disable:4786 )
#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;

typedef struct
{
	int pre; //到达该状态的前一状态
	int move; //到达该状态的操作
	int existed; //该状态是否出现过
}State;

typedef struct
{
	string s;
	int pos;
}Node;

const int MAX_N = 362884;

int go[ 4 ][ 2 ] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; //右下左上(0123)
State state[ MAX_N ];
string str;
string dest( "123456780" );
char num[ 4 ];

void swap_2( char& a, char& b )
{
	char t = a;
	a = b;
	b = t;
}

void init()
{
	int i;
	
	str.erase( str.begin(), str.end() );
	str += num;
	for( i = 2; i <= 9; ++i )
	{
		scanf( "%s", num );
		if( num[ 0 ] == 'x' )
			num[ 0 ] = '0';
		str += num;
	}
}

int find_pos( const string& s )
{
	int i;
	for( i = 0; i < s.size(); ++i )
		if( s[ i ] == '0' )
			return i;

	return -1;
}

/*
	因为BFS是从目的态出发，所以move是指从目的态到其它态的操作	
	因此从目的态到其它态的操作是反操作，右变成了左，上变成了下
*/
char change( int i )
{
	switch( i )
	{
	case 0:
		return 'l';
	case 1:
		return 'u';
	case 2:
		return 'r';
	case 3:
		return 'd';
	}
	return 'w';
}

/*
	哈希函数：本题难点。
	全排列的哈希：对应位的逆序数乘以对应位的阶乘数(从0!开始)即为哈希值(0~n!-1)，
	可以保证哈希数在0~n!-1之间且唯一。

	如：1 2 3 的全排列的哈希
	1 2 3	0 * 0! + 0 * 1! + 0 * 2! = 0
	1 3 2	0 * 0! + 0 * 1! + 1 * 2! = 2
	2 1 3	0 * 0! + 1 * 1! + 0 * 2! = 1
	2 3 1	0 * 0! + 0 * 1! + 2 * 2! = 4
	3 1 2	0 * 0! + 1 * 1! + 1 * 2! = 3
	3 2 1	0 * 0! + 1 * 1! + 2 * 2! = 5
*/
int get_key( const string& s )
{
	int i, j;
	int cnt;
	int n = 1;
	int m = 1;
	int res = 0;

	/*求逆序数*/
	for( i = 1; i < s.size(); ++i ) //第一个的逆序数必为0
	{
		cnt = 0;
		for( j = 0; j < i; ++j )
		{
			if( s[ i ] < s[ j ] ) //后边的比前边的小，逆序
				++cnt;	
		}
		res += cnt * m;
		++n;
		m = m * n;
	}
	return res;
}

/*
从目的往回求，一次性求出所有状态。以后只要哈希到该状态，直接输出
如果求后检测到existed仍为初值(-1),则表示该状态为不可能到达态
*/
void BFS()
{
	queue<Node> q;
	Node cur, next;
	int i;

	memset( state, -1, sizeof( state ) );
	cur.s = dest;
	cur.pos = find_pos( dest );
	int k = get_key( dest );
	state[ k ].existed = 1;
	state[ k ].pre = -1; //树根结点，无父结点
	q.push( cur );
	while( !q.empty() )
	{
		cur = q.front();
		q.pop();
		int cur_r = cur.pos / 3;
		int cur_c = cur.pos % 3;
		int cur_key = get_key( cur.s );
		for( i = 0; i < 4; ++i )
		{
			int next_r = cur_r + go[ i ][ 0 ];
			int next_c = cur_c + go[ i ][ 1 ];
			
			if( next_r >= 0 && next_r < 3		//这里可以用围墙来避免界限判断的
				&& next_c >= 0 && next_c < 3 ) //和写推箱子游戏一样呀!!汗。。。
			{
				next.s = cur.s;
				next.pos = next_r * 3 + next_c;
				swap_2( next.s[ cur.pos ], next.s[ next.pos ] );	
				int next_key = get_key( next.s );
				if( state[ next_key ].existed == -1 ) //未出现过
				{
					state[ next_key ].move = i;
					state[ next_key ].pre = cur_key;
					state[ next_key ].existed = 1;
					q.push( next );				
				}
			}
		}
	}
}

void solve()
{
	int key = get_key( str );
	if( state[ key ].existed == -1 )
	{
		printf( "unsolvable\n" );
		return;
	}

	string res;
	while( state[ key ].pre != -1 )
	{
		res += change( state[ key ].move );
		key = state[ key ].pre;
	}
	puts( res.c_str() );
}

int main()   
{   
	
#ifndef ONLINE_JUDGE     
	   FILE *fin;
	
       fin = freopen( "t.in", "r", stdin );
	   freopen( "t.out", "w", stdout );
       if( !fin )
       {
       		printf( "reopen in file failed...\n" );   
   			exit( 0 );
       }
#endif

	BFS();
	while( scanf( "%s", num ) != EOF )
	{
		init();
		solve();
	}


#ifndef ONLINE_JUDGE      
       fclose( stdin );   
#endif   
       return 0;   
}