#include <stdio.h>
#include <stdlib.h>
#define base 100000000
int target = 123456780;

int input[9];
int n = 3;
int nSq = 9;

int qh = 0; qt = 0;
long long queue[200000];
int qLength = 200000;

int max = 200000;
int T[200000];

typedef struct node {
	struct node* parent;
	int hash;
} node_t;

node_t* source = NULL;

node_t* newNode(int);
int toState(int[]);
void* toArray(int*, int);

int getZeroPos(int);
int swap(int, int, int);
int getNext(long long*, node_t*);

void getPath(node_t*);

void bfs(node_t*);

int isEmpty();
void enqueue(node_t*);
node_t* dequeue();

int hashSearch(int);
int hashInsert(int);
int hash(int, int);

int main() {
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)	scanf("%d", &input[i * n + j]);
	}
	int state = toState(input);
	if (state == target) {
		printf("0\n");
		return 0;
	}
	int hashK = hashInsert(state);
	source = newNode(hashK);
	bfs(source);

	return 0;
}

node_t* newNode(int hashK) {
	node_t* node = (node_t*)malloc(sizeof(node_t));
	node->parent = NULL;
	node->hash = hashK;
	return node;
}

int toState(int from[]) {
	int result = 0;
	int weight = base;

	for (int i = 0; i < (n * n); i++) {
		result += from[i] * weight;
		weight /= 10;
	}
	return result;
}

void* toArray(int* store, int state) {
	int weight = base;

	for (int i = 0; i < (n * n); i++) {
		store[i] = (int)(state / weight);
		state %= weight;
		weight /= 10;
	}
}

int getZeroPos(int state) {
	int weight = base;
	for (int i = 0; i < nSq; i++) {
		if (state / weight == 0) return i;
		state %= weight;
		weight /= 10;
	}
	exit(0);
}

int swap(int originalState, int zero_pos, int with_pos) {
	int newState;
	int swapArray[9];
	toArray(&swapArray, originalState);

	int temp = *(swapArray + with_pos);
	*(swapArray + with_pos) = *(swapArray + zero_pos);
	*(swapArray + zero_pos) = temp;

	newState = toState(swapArray);

	return newState;
}

int getNext(long long* states, node_t* current) {
	int count = 0;

	int current_state = T[current->hash];

	int zero_pos = getZeroPos(current_state);
	int row = zero_pos / n;
	int col = zero_pos % n;

	if (row != 0) {	//swap with above
		int newState = swap(current_state, zero_pos, zero_pos - 3);

		if (hashSearch(newState) == -1) {
			int newHash = hashInsert(newState);

			node_t* add = newNode(newHash);
			add->parent = current;

			states[count] = add;
			count++;
		}
	}
	if (row != 2) {	//swap with below
		int newState = swap(current_state, zero_pos, zero_pos + 3);

		if (hashSearch(newState) == -1) {
			int newHash = hashInsert(newState);

			node_t* add = newNode(newHash);
			add->parent = current;

			states[count] = add;
			count++;
		}
	}
	if (col != 0) {	//swap with left
		int newState = swap(current_state, zero_pos, zero_pos - 1);

		if (hashSearch(newState) == -1) {
			int newHash = hashInsert(newState);

			node_t* add = newNode(newHash);
			add->parent = current;

			states[count] = add;
			count++;
		}
	}
	if (col != 2) {	//swap with right
		int newState = swap(current_state, zero_pos, zero_pos + 1);

		if (hashSearch(newState) == -1) {
			int newHash = hashInsert(newState);

			node_t* add = newNode(newHash);
			add->parent = current;

			states[count] = add;
			count++;
		}
	}
	return count;
}

void getPath(node_t* from) {
	int distance = 0;
	node_t* cur = from;
	while (cur->parent != NULL) {
		cur = cur->parent;
		distance++;
	}
	printf("%d\n", distance);
	exit(0);
}

void bfs(node_t* start) {
	enqueue(start);

	while (!isEmpty()) {
		node_t* init = dequeue();
		long long states[4];
		int length = getNext(&states, init);

		for (int i = 0; i < length; i++) {
			node_t* cur = states[i];
			if (T[cur->hash] == target)	getPath(cur);
			enqueue(cur);
		}
	}
}


int isEmpty() {
	if (qt == qh) return 1;
	return 0;
}

void enqueue(node_t* x) {
	queue[qt] = x;
	if (qt + 1 == qLength) qt = 0;
	else qt++;
}

node_t* dequeue() {
	node_t* x = queue[qh];
	if (qh + 1 == qLength) qh = 0;
	else qh++;
	return x;
}


int hashInsert(int k) {
	int i = 0;
	while (1) {
		int hashKey = hash(k, i);
		if (T[hashKey] == 0) {
			T[hashKey] = k;
			return hashKey;
		}
		i++;
	}
	return -1;
}

int hashSearch(int k) {
	int i = 0;
	while (1) {
		int hashKey = hash(k, i);
		if (T[hashKey] == k) return hashKey;
		if (T[hashKey] == 0) return -1;
		if (i >= max) exit(10);
		i++;
	}
	return -1;
}

int hash(int k, int i) {
	int hash1 = k % 199999;
	int hash2 = 1 + k % 199967;
	int ans = ((hash1 + i * hash2) % 199999);
	if (ans < 0) ans *= -1;
	return ans;
}




Measured memory_bytes: 9616