#include <iostream>
int maxDepth = 0;
bool isAbleToSolve = false;
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, -1, 1, 0 };
const std::string table[9] = { "x", "1", "2", "3", "4", "5", "6", "7", "8" };
std::string start, goal = "12345678x";
int Abs(int val)
{
if (val < 0) return -val;
return val;
}
int GetH(std::string now)
{
int hCost = 0, lth = now.length();
int goalPos, nowPosX, nowPosY, goalPosX, goalPosY;
// Except 0.
for (int i = 0; i < lth; i++)
{
if (now[i] == 'x') continue;
goalPos = goal.find(now[i]);
nowPosX = i / 3, nowPosY = i % 3;
goalPosX = goalPos / 3, goalPosY = goalPos % 3;
hCost += Abs(nowPosX - goalPosX) + Abs(nowPosY - goalPosY);
}
return hCost;
}
void IDAStar(int depth, std::string board, int prevPos)
{
int h = GetH(board);
if (h == 0)
{
isAbleToSolve = true;
return;
}
if (depth + h > maxDepth)
{
return;
}
int zeroPos = board.find(table[0]);
int zx = zeroPos / 3, zy = zeroPos % 3;
for (int i = 0; i < 4; i++)
{
int nx = zx + dx[i], ny = zy + dy[i];
int newPos = nx * 3 + ny;
if (nx < 0 || ny < 0 || nx >= 3 || ny >= 3 || newPos == prevPos)
continue;
std::string next = board;
std::swap(next[newPos], next[zeroPos]);
// std::cout << next << std::endl;
IDAStar(depth + 1, next, zeroPos);
}
return;
}
int main()
{
char input;
for (int i = 1; i <= 9; i++)
{
std::cin >> input;
start.append(1, input);
}
while (true)
{
isAbleToSolve = false;
IDAStar(0, start, -1);
if (maxDepth >= 32)
{
std::cout << "-1" << std::endl;
break;
}
if (isAbleToSolve)
{
std::cout << maxDepth << std::endl;
break;
}
// std::cout << maxDepth << " failed." << std::endl;
maxDepth++;
}
return 0;
}