/*
雙向BFS就是從起點 和 終點 同時開始搜尋。由起點搜尋(BSF1)得到的點标記為1，
由終點搜尋(BFS2)得到的點标記為2。當某一時刻BFS1搜尋到了已經标記為2的點(或BFS2搜到
了1号點)，說明發生相遇，那麼答案就是由bfs1和bfs2分别求得的兩段路徑長度的和。
簡單的分析：設每次的BFS，總的搜尋狀态數是r^L(r是搜尋的分支數，L是搜尋層數)。而采
取雙向BFS算法，那麼，從前往後、從後往前，分别需要搜尋L/2層，合起來就是2*(r^(L/2))
這要比一般的BFS快的多。
可以看到，雙向BFS不過就是在while循環中套了兩個節點擴充子產品，一個是qu1，一個是qu2
二者輪流執行、輪流擴充。qu1擴充一次，然後qu2擴充一次，直到二者中有點相遇為止。
*/
//poj 1077 Eight
#include <iostream> //雙向bfs和康托壓縮
#include <deque>
#include<string>
#include<cmath>
using namespace std;
int visited[1000000];
int fac[]={1,1,2,6,24,120,720,5040,40320,362880}; //9!表
string path1[1000000],path2[1000000];
int cantor(int arr[])
{
int temp,num=1;
for(int i=0;i<9;++i)
{
temp=0;
for(int j=i+1;j<9;++j)
if(arr[j]<arr[i])
temp++;
num+=fac[8-i]*temp;
}
return num;
}
void to_arr(int list[],int num)
{
int i;
for(i=0;i<9;++i)
list[i]=0;
i=8;
while(num)
{
list[i--]=num%9;
num/=9;
}
}
int to_num(int list[])
{
int n=0;
for(int i=0;i<9;++i)
n=n*9+list[i];
return n;
}
int move[4]={-3,3,1,-1};
char pos[4]={'u','d','r','l'};
struct node //空間開銷是58276K
{
string state;
int num;
int sub;
node(string str,int n,int dir,int s)
{
int arr[9];
to_arr(arr,n);
num=n;
state=str;
if(dir==0)
sub=s;
else
{
state.push_back(pos[dir-1]);
swap(arr[s+move[dir-1]],arr[s]);
num=to_num(arr);
sub=s+move[dir-1];
}
}
};
deque<node> forword,backword;
int main()
{
int arr[9]={1,2,3,4,5,6,7,8,0},loc;
node bck("",to_num(arr),0,8);
backword.push_back(bck);
char ch;
for(int i=0;i<9;++i)
{
cin>>ch;
if(ch=='x')
arr[i]=0,loc=i;
else
arr[i]=int(ch-48);
}
node forw("",to_num(arr),0,loc);
forword.push_back(forw);
while(!forword.empty())
{
node temp=forword.front();
forword.pop_front();
to_arr(arr,temp.num);
int d=cantor(arr);
if(visited[d]==2)
{
cout<<temp.state;
for(int k=path2[d].size()-1;k>=0;--k)
{
ch=path2[d][k];
if(ch=='u')
cout<<'d';
else if(ch=='d')
cout<<'u';
else if(ch=='r')
cout<<'l';
else
cout<<'r';
}
cout<<endl;
return 0;
}
else if(visited[d]==0)
{
visited[d]=1;
path1[d]=temp.state;
if(temp.sub>=3)
{
node puzzle(temp.state,temp.num,1,temp.sub);
forword.push_back(puzzle);
}
if(temp.sub<6)
{
node puzzle(temp.state,temp.num,2,temp.sub);
forword.push_back(puzzle);
}
if(temp.sub%3!=2)
{
node puzzle(temp.state,temp.num,3,temp.sub);
forword.push_back(puzzle);
}
if(temp.sub%3!=0)
{
node puzzle(temp.state,temp.num,4,temp.sub);
forword.push_back(puzzle);
}
}
if(!backword.empty())
{
node temp=backword.front();
backword.pop_front();
to_arr(arr,temp.num);
int d=cantor(arr);
if(visited[d]==1)
{
cout<<path1[d];
for(int k=temp.state.size()-1;k>=0;--k)
{
ch=temp.state[k];
if(ch=='u')
cout<<'d';
else if(ch=='d')
cout<<'u';
else if(ch=='r')
cout<<'l';
else
cout<<'r';
}
cout<<endl;
return 0;
}
else if(visited[d]==0)
{
visited[d]=2;
path2[d]=temp.state;
if(temp.sub>=3) //u d r l
{
node puzzle(temp.state,temp.num,1,temp.sub);
backword.push_back(puzzle);
}
if(temp.sub<6)
{
node puzzle(temp.state,temp.num,2,temp.sub);
backword.push_back(puzzle);
}
if(temp.sub%3!=2)
{
node puzzle(temp.state,temp.num,3,temp.sub);
backword.push_back(puzzle);
}
if(temp.sub%3!=0)
{
node puzzle(temp.state,temp.num,4,temp.sub);
backword.push_back(puzzle);
}
}
}
}
cout<<"unsolvable\n";
return 0;
}
