#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<queue>
using namespace std;
string s;
typedef pair<int, string> PII;
typedef pair<int, PII> PIII;
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
int sorce, exnum; string mystring;
unordered_map<string, string> mp;//因为任意一个点只遍历一次,直接用map来输出正确答案,不用逆推。
inline int exp(string str)//计算其理想操作距离
{
int tot = 0;
for (int i = 0; i <= 8; i++)
{
if (str[i] == 'x')continue;
int a = str[i] - '0'; a--;
tot += abs(a % 3 - i % 3) + abs(a / 3 - i / 3);
}
return tot;
}
//四个方向
inline void up(string ss,int i,int sorce,int exnum)
{
string temp = mp[ss];
swap(ss[i], ss[i - 3]);
temp += 'u';
if (mp[ss].size() <= temp.size() && mp[ss] != "")
{
return;
}
else
{
mp[ss] = temp;
}
int step = sorce - exnum + 1;
exnum = exp(ss);
heap.push({ step + exnum,{exnum,ss } });
}
inline void down(string ss, int i, int sorce, int exnum)
{
string temp = mp[ss];
swap(ss[i], ss[i + 3]);
temp += 'd';
if (mp[ss].size() <= temp.size() && mp[ss] != "")
{
return;
}
else
{
mp[ss] = temp;
}
int step = sorce - exnum + 1;
exnum = exp(ss);
heap.push({ step + exnum,{exnum,ss } });
}
inline void left(string ss, int i, int sorce, int exnum)
{
string temp = mp[ss];
swap(ss[i], ss[i - 1]);
temp += 'l';
if (mp[ss].size() <= temp.size() && mp[ss] != "")
{
return;
}
else
{
mp[ss] = temp;
}
int step = sorce - exnum + 1;
exnum = exp(ss);
heap.push({ step + exnum,{exnum,ss } });
}
inline void right(string ss, int i, int sorce, int exnum)
{
string temp = mp[ss];
swap(ss[i], ss[i + 1]);
temp += 'r';
if (mp[ss].size() <= temp.size() && mp[ss] != "")//如果已经有更小的步数就不更新,如果之前记录的步数比他大就更新成小的
{
return;
}
else
{
mp[ss] = temp;
}
int step = sorce - exnum + 1;
exnum = exp(ss);
heap.push({ step + exnum,{exnum,ss } });
}
inline int found(string ss)//找到x的位置并且返回下标
{
for (int i = 0; i <= 8; i++)
{
if (ss[i] == 'x')
{
return i;
}
}
return 0;
}
int astar()
{
while (1)
{
sorce = heap.top().first;
exnum = heap.top().second.first;
mystring = heap.top().second.second;
heap.pop();
if (mystring == "12345678x")
{
cout << mp[mystring] << endl;
return 0;
}
int i = found(mystring);
if (i >= 3)up(mystring, i, sorce, exnum);
if (i >= 1 && i != 3 && i != 6)left(mystring, i, sorce, exnum);
if (i <= 5)down(mystring, i, sorce, exnum);
if (i <= 7 && i != 5 && i != 2)right(mystring, i, sorce, exnum);
}
return 0;
}
int main()
{
string s3 = "";
for (int i = 0; i < 9; i++)
{
char s2; cin >> s2;
s += s2;
if (s2 != 'x')s3 += s2;
}
//进行初始化操作
int numbs = exp(s);
mp[s] = "";
heap.push({ numbs,{numbs,s } });
//判断是否有解
int cnt = 0;
for (int i = 0; i < 8; i++) {
for (int j = i; j < 8; j++) {
if (s3[i] > s3[j]) cnt++;
}
}
if (cnt & 1) cout << "unsolvable" << endl;
else astar();
//确认有解后开始a*
return 0;
}