#include<bits/stdc++.h>
using namespace std;

struct queen
{
	int g[4][4];
	int ox, oy;
	int cnt;
}qu[10005], a;

int end_[4][4] = {{1, 2, 3}, 
				  {8, 0, 4},
				  {7, 6, 5}};
int cx[5] = {0, -1, 1, 0, 0};
int cy[5] = {0, 0, 0, 1, -1};

bool end(queen a)
{
	int i;
	for(i = 0; i < 9; i++)
	{
		if(a.g[i / 3][i % 3] != end_[i / 3][i % 3])	return false;
	}
	return true;
}

bool again(queen a, int tail)
{
	int i, j;
	bool flag;
	for(j = 1; j <= tail; j++)
	{
		flag = false;
		for(i = 0; i < 9; i++)
		{
			if(a.g[i / 3][i % 3] != qu[j].g[i / 3][i % 3])	{flag = true; continue;}
		}
		if(!flag) return true;
	}
	return false;
}

int bfs()
{
	int x, y;
	int i;
	int l = 0, r = 1;
	while(l < r)
	{
		l++;
		for(i = 1; i <= 4; i++)
		{
			
			a = qu[l];			
			x = a.ox + cx[i];
			y = a.oy + cy[i];
			if(x > 2 || x < 0 || y > 2 || y < 0)	continue;
			a.g[a.ox][a.oy] = a.g[x][y];
			a.g[x][y] = 0;
			a.ox = x; a.oy = y;			
			a.cnt++;
			if(end(a) == 1)	
			{
				cout << a.cnt - 1; 
				return 0;
			}
			if(again(a, l) == 0)a
			{
				r++;
				qu[r] = a;
			}
		}
	}
}

int main()
{

	int i, j;
	char c;
	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++)
		{
			cin >> c;
			qu[1].g[i][j] = c - '0';
			if(c == '0')
			{
				qu[1].ox = i;
				qu[1].oy = j;
			}
		}
		qu[1].cnt = 1;	
	if(end(qu[1]))	{printf("1");	return 0;}
	else	bfs();
}
![多美呀](http://m.qpic.cn/psc?/V12tJTSl1laogw/Sc7wZG8Q0BUeMz.O80ebfM*RmpVw1Rx0BQCqKuvD8VnKjbjkkXx9pvGiBwNq8G9kuE0kcV*Qv17XbNQkKKfsRWtzemX2YwKSYVZRjMEevb0!/b&bo=8wJBAgAAAAADF4A!&rf=viewer_4)