#include <bits/stdc++.h>

using namespace std;

typedef complex<int> P;
typedef long long ll;

P Dir[4] = {
	P(-1, 0),
	P(0, -1),
	P(1, 0),
	P(0, 1),
};

ll pow17[15];

void Init() {
	pow17[0] = 1;
	for (int i = 1; i < 15; ++i) {
		pow17[i] = pow17[i-1]*17;
	}
}

class Puzzle {
private:
	int W, H;
	int holes;
	int board[4][4];
	int coe[4][4];
	map<int, P> rboard;
	ll hash, gHash;

public:
	Puzzle(int W, int H) : W(W), H(H) {
		init();
	}
	void init() {
		holes = 0;
		rboard.clear();
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				int k = y * W + x + 1;
				board[y][x] = k;
			}
		}
		initCoe();
		initHash();
	}
	void setTile(int x, int y, int v) {
		int pv = board[y][x];
		if (pv < 0) --holes;
		if (v < 0) ++holes;
		board[y][x] = v;
		rboard[v] = P(x, y);
		hash += ((v < 0 ? 0 : v) - (pv < 0 ? 0 : pv)) * pow17[coe[y][x]];
	}
	void initCoe() {
		for (int y = 0, k = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				if (getTile(x, y) != 0) {
					coe[y][x] = k++;
				}
				else {
					coe[y][x] = -1;
				}
			}
		}

		gHash = 0;
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				int v = getTile(x, y);
				if (v > 0) {
					int x = (v-1)%W, y = (v-1)/W;
					gHash += v * pow17[coe[y][x]];
				}
			}
		}
	}
	int getTile(int x, int y) {
		return board[y][x];
	}
	bool swap(int x1, int y1, int x2, int y2) {
		int v1 = getTile(x1, y1), v2 = getTile(x2, y2);
		if (v1 == 0 || v2 == 0 || (v1 < 0 && v2 == 0)) return false;
		setTile(x1, y1, v2);
		setTile(x2, y2, v1);
		return true;
	}
	bool isComplete() {
		return hash == gHash;
/*
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				int k = y * W + x + 1;
				int v = board[y][x];
				if (v > 0 && k != v) return false;
			}
		}
		return true;
*/
	}
	bool isOut(int x, int y ) {
		return x < 0 || x >= W || y < 0 || y >= H;
	}
	void move(int dir) {
		dir = (dir + 2) % 4;
		vector< pair<P, int> > v;
		for (int i = 0; i < holes; ++i) {
			P& p = rboard[-(i+1)];
			int x = p.real(), y = p.imag();
			int nx = x + Dir[dir].real(), ny = y + Dir[dir].imag();
			if (isOut(nx, ny)) continue;
			if (getTile(nx, ny) < 0) continue;
			v.push_back( pair<P, int>(p, getTile(nx, ny)) );
		}
		for (int i = 0; i < v.size(); ++i) {
			int x = v[i].first.real(), y = v[i].first.imag();
			P p = rboard[v[i].second];
			swap(x, y, p.real(), p.imag());
		}
	}
	void draw() {
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				if (x) cout << " ";
				printf("%2d", getTile(x, y));
			}
			cout << endl;
		}
	}
	ll getHash() {
		return hash;
	}
	void initHash() {
		hash = 0;
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				int v = getTile(x, y);
				if (v != 0) {
					hash += (v < 0 ? 0 : v) * pow17[coe[y][x]];
				}
			}
		}
	}
	void setHash(ll h) {
		int k = 0;
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				if (getTile(x, y) != 0) {
					int v = h%17; if (v == 0) v = --k;
					setTile(x, y, v);
					h /= 17;
				}
			}
		}
	}
	int getH() {
		int res = 0;
		for (int y = 0; y < H; ++y) {
			for (int x = 0; x < W; ++x) {
				int v = getTile(x, y);
				if (v > 0) {
					int gx = (v-1)%W, gy = (v-1)/W;
					res += abs(gx-x) + abs(gy-y);
				}
			}
		}
		return res;
	}
	int getHoles() {
		return holes;
	}
	ll getGHash() {
		return gHash;
	}
};

struct Node {
	ll hash;
	int step, h;
};
bool operator >(const Node& n1, const Node& n2) {
	return n1.h > n2.h;
}

int main() {
	Init();

//	int W, H; cin >> W >> H;
	int W = 3, H = 3;
	Puzzle puzzle(W, H);
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) {
			int v; cin >> v;
			if (v == 0) v = -1;
			puzzle.setTile(x, y, v);
		}
	}
	puzzle.initCoe();
	puzzle.initHash();

	int s = 0;

	set<ll> gone;
	priority_queue<Node, vector<Node>, greater<Node> > Q; Q.push((Node){puzzle.getHash(), 0, puzzle.getH()});
	while ( !Q.empty() ) {
		Node node = Q.top(); Q.pop();
		ll hash = node.hash;
		int step = node.step;

		if (step > s) {
//			s = step;
//			cout << s << endl;
		}

		if (gone.count(hash)) continue;
		gone.insert(hash);

		if (puzzle.getGHash() == hash) {
			cout << step << endl;
			break;
		}

		for (int i = 0; i < 4; ++i) {
			puzzle.setHash(hash);
			puzzle.move(i);
			ll h = puzzle.getHash();
			if (gone.count(h) == 0) {
				Q.push((Node){h, step+1, step*puzzle.getHoles()+puzzle.getH()});
			}
		}
	}
}

Measured memory_bytes: 1796