#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define SENTINEL 1000000001

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

typedef pair<int, int> pii;

struct State
{
	int puzzle[9];
	int depth;
	int evaluation;

	bool operator<(const State& s)const
	{
		return evaluation < s.evaluation;
	}

	bool operator>(const State& s)const
	{
		return evaluation > s.evaluation;
	}

	bool operator==(const State& s)const
	{
		for (int i = 0; i < 9; i++)
		{
			if (puzzle[i] != s.puzzle[i])
			{
				return false;
			}
		}
		return true;
	}
};

State goal;
vector<State> checkedState;

int heuristic(State s)
{
	int eva = 0;
	int pos1[9], pos2[9];
	for (int i = 0; i < 9; i++)
	{
		pos1[s.puzzle[i]] = i;
		pos2[goal.puzzle[i]] = i;
	}
	for (int i = 0; i < 9; i++)
	{
		int manhattan = 0;
		manhattan += abs(pos1[i] / 3 - pos2[i] / 3);
		manhattan += abs(pos1[i] % 3 - pos2[i] % 3);
		eva += manhattan;
	}
	return eva;
}

int solve(State start)
{
	priority_queue<State, vector<State>, greater<State>> pq;

	pq.push(start);

	while (!pq.empty())
	{
		State ts = pq.top();
		pq.pop();

		checkedState.push_back(ts);

		if (ts == goal)
		{
			return ts.depth;
		}

		int zeroi = -1;
		for (int i = 0; i < 9; i++)
		{
			if (ts.puzzle[i] == 0)
			{
				zeroi = i;
				break;
			}
		}

		if (zeroi <= 5)
		{
			State tts = ts;
			int t = tts.puzzle[zeroi];
			tts.puzzle[zeroi] = tts.puzzle[zeroi + 3];
			tts.puzzle[zeroi + 3] = t;
			tts.depth++;
			tts.evaluation = heuristic(tts) + tts.depth;
			if (find(checkedState.begin(), checkedState.end(), tts) == checkedState.end())
			{
				pq.push(tts);
			}
		}
		if (zeroi % 3 != 2)
		{
			State tts = ts;
			int t = tts.puzzle[zeroi];
			tts.puzzle[zeroi] = tts.puzzle[zeroi + 1];
			tts.puzzle[zeroi + 1] = t;
			tts.depth++;
			tts.evaluation = heuristic(tts) + tts.depth;
			if (find(checkedState.begin(), checkedState.end(), tts) == checkedState.end())
			{
				pq.push(tts);
			}
		}
		if (zeroi % 3 != 0)
		{
			State tts = ts;
			int t = tts.puzzle[zeroi];
			tts.puzzle[zeroi] = tts.puzzle[zeroi - 1];
			tts.puzzle[zeroi - 1] = t;
			tts.depth++;
			tts.evaluation = heuristic(tts) + tts.depth;
			if (find(checkedState.begin(), checkedState.end(), tts) == checkedState.end())
			{
				pq.push(tts);
			}
		}
		if (3 <= zeroi)
		{
			State tts = ts;
			int t = tts.puzzle[zeroi];
			tts.puzzle[zeroi] = tts.puzzle[zeroi - 3];
			tts.puzzle[zeroi - 3] = t;
			tts.depth++;
			tts.evaluation = heuristic(tts) + tts.depth;
			if (find(checkedState.begin(), checkedState.end(), tts) == checkedState.end())
			{
				pq.push(tts);
			}
		}
	}

	return -1;
}

int main()
{
	State start;

	goal.depth = 0;
	goal.evaluation = 0;
	for (int i = 0; i < 9; i++)
	{
		goal.puzzle[i] = (i + 1) % 9;
	}

	for (int i = 0; i < 9; i++)
	{
		int n;
		cin >> n;

		start.puzzle[i] = n;
	}

	start.depth = 0;
	start.evaluation = 0;

	printf("%d\n", solve(start));
	
	return 0;
}


Measured memory_bytes: 4924