#include
#include
#include
using?namespace?std;

typedef?struct?node
{
	int?a[3][3];
	int?value;???//value??表示f（n）=d（n）+w（n）
	int?height;??//搜索到當前節(jié)點的高度
	int?from;???//表示該節(jié)點是由何種移動所得，1左移，2右移，3上移，4下移
	char?path[1000];?????//保存前面搜索路徑
	friend?bool?operator?	{
		return?t1.value>t2.value;???//最小值優(yōu)先
	}
}node*nodelist;

class?eightnum
{
public:
	eightnum（）
	{
		int?ij;
		for（i=0;i<3;i++）
		{
			for（j=0;j<3;j++）
			{
				cin>>a[i][j];
				if（a[i][j]==0）????//空格處置為9，便于后面比較求value
					a[i][j]=9;
			}
		}
		flag=0;
		height=0;
	}
	
	bool?eightcan（）????//判斷八數(shù)碼問題可否有解
	{
		/*
		判斷給出的排列是否能夠通過有限次移動，達到目標狀態(tài)。
		算法支持：
		首先指定Less（k）k表示在九宮格中的某個數(shù)字k的取值范圍是1~9Less（k）
		表示為k所在九宮格位置之后比k小的數(shù)字的個數(shù)。k=0時，自動轉(zhuǎn)換成k=9。
		在下列排列中
		1?0?3
		7?2?4
		6?8?5
		Less（1）=0Less（9）=7Less（3）=1Less（7）=4Less（2）=0Less（4）=0
		Less（6）=1Less（8）=0Less（5）=0
		設(shè)定ij表示空格位置在九宮格中的位置，此例中i=1j=2。
		判斷排列是否可在有限次移動得到解的條件是
		k=1:9;
		（sum（Less（k））+i+j）%2==0
		*/
		int?b[9];????????????????????//將二維數(shù)組轉(zhuǎn)化成一維數(shù)組便于操作
		int?ijkxy;???????????????//ijk為控制變量，xy表示空格位置的橫坐標與縱坐標
		//二維數(shù)組轉(zhuǎn)一維數(shù)組
		k=0;
		for（i=0;i<3;i++）??????????????
		{
			for（j=0;j<3;j++）
			{
				b[k]=a[i][j];
				if（a[i][j]==9）
				{
					x=i+1;
					y=j+1;
				}
				k++;
			}
		}
		//求k=1:9;sum（Less（k））+i+j	
		int?sum=x+y;??????????????????	
		for（i=0;i<9;i++）
		{
			for（j=i;j<9;j++）
			{
				if（b[j]					sum++;
			}
		}
		if（sum%2==0）
			return?true;
		else
			return?false;		
	}
	
	int?f（node?now_node）????
	{
		/*求解該節(jié)點的f（n）=d（n）+w（n），在構(gòu)造時已經(jīng)將d（n）求出，
		為n.height且n.value<<=n.heightw（n）表示該節(jié)點與目標狀態(tài)節(jié)點
		不同的個數(shù)*/
		int?ij;
		int?value=0;
		for（i=0;i<3;i++）
		{
			for（j=0;j<3;j++）
				if（now_node.a[i][j]!=i*3+j+1）
				{
					value++;
				}
		}
		return?value+now_node.value;
	}
	
	int?solution（）
	{
		if（!eightcan（））????????????//判斷該排列是否能夠達到目標狀態(tài)
		{
			cout<<“該種排列無法移動得到目標狀態(tài)“<			return?0;
		}
		int?ijxy;
		priority_queue?q;?????//構(gòu)造優(yōu)先權(quán)隊列，以value值最小的優(yōu)先出隊
		node?p_first;
		for（i=0;i<3;i++）
		{
			for（j=0;j<3;j++）
				p_first.a[i][j]=a[i][j];
		}
		p_first.value=0;
		p_first.height=0;
		p_first.from=0;
		p_first.path[0]=48;
		p_first.path[1]=0;
		p_first.value=f（p_first）;
		if（resultOK（p_first）==1）?????//如果初始狀態(tài)即為目標狀態(tài)直接輸出
		{
			height=p_first.height;
			path[0]=p_first.path[0];
			path[1]=p_first.path[1];
			return?1;
		}
		q.push（p_first）;
		while（q.empty（）==false）
		{	
			//獲得當前擴展節(jié)點的空格位置
			for（i=0;i<3;i++）
			{
				for（j=0;j<3;j++）
					if（q.top（）.a[i][j]==9）
					{
						x=i;y=j;
					}
			}
			//進行移動操作
			if（y-1>=0?&&?q.top（）.from!=2）
				q.push（*moveleft（q.top（）xy））;
			if（flag==1）
				break;
			if（y+1<=2?&&?q.top（）.from!=1）
				q.push（*moveright（q.top（）xy））;
			if（flag==1）
				break;
			if（x-1>=0?&&?q.top（）.from!=4）
				q.push（*moveup（q.top（）xy））;
			if（flag==1）
				break;
			if（x+1<=2?&&?q.top（）.from!=3）