#include?
#include?
#include?
#include?
#include?
#define?MAXDEEP?5
using?namespace?std;
struct?state
{
	int?numfadeep;
	int?sta[9];
};
int?st[9]={283104765};
int?ta[9]={123804765};
stack?open;
queue?close;
void?putopen（int?st[]）
{
	int?i;
	state?star;
	star.fa=-1;//根節(jié)點的父節(jié)點沒有，設置為-1，以表區(qū)別
	star.num=1;//每個狀態(tài)的標志
	star.deep=0;//根節(jié)點深度為0
	for（i=0;i<9;i++）
	{
		star.sta[i]=st[i];
	}
	open.push（star）;
}
bool?ablepush（state?op）
{
	state?temp;
	int?ij;
	stack?cp1;
	queue?cp2;
	while（!open.empty（））
	{
		temp=open.top（）;
		for（i=0;i<9;++i）
			if（temp.sta[i]!=op.sta[i]）?
				break;
			if（i==8）?return?false;
			open.pop（）;
			cp1.push（temp）;
	}
	while（!cp1.empty（））
	{
		temp=cp1.top（）;
		cp1.pop（）;
		open.push（temp）;
	}
	for（i=0;i	{
		temp=close.front（）;
		close.pop（）;
		cp2.push（temp）;
		close.push（temp）;
	}
	while（!cp2.empty（））
	{
		i++;
		for（j=0;j<9;j++）
		{
			if（cp2.front（）.sta[j]!=op.sta[j]）
			{
				cp2.pop（）;
				break;	
			}
			if（j==8）?return?false;
		}
	}
	return?true;	
}

bool?istarget（state?t）
{
	int?i;
	for（i=0;i<9;i++）
		if（t.sta[i]!=ta[i]）
			return?false;
		return?true;
}

int?Move（state?op）//op為close表中將進行上、下、左、右移動的狀態(tài)
{
	int?izerodp;
	int?temp1temp2temp3temp4;
	dp=op.deep+1;//進行MOVE函數(shù)則深度+1
	for（i=0;i<9;++i）//找到0點
		if（op.sta[i]==0）??
		{zero=i;break;}
		if（zero!=0?&&?zero!=3?&&?zero!=6）//左移
		{
			state?op1=op;
			temp1=op1.sta[zero];
			op1.sta[zero]=op1.sta[zero-1];
			op1.sta[zero-1]=temp1;
			if（ablepush（op1））
			{
				op1.deep=dp;
				op1.fa=op.num;
				open.push（op1）;
				if（istarget（op1））
					return?op1.fa;	
			}
		}	
		if（zero!=0?&&?zero!=1?&&?zero!=2）//上移
		{
			state?op2=op;
			temp2=op2.sta[zero];
			op2.sta[zero]=op2.sta[zero-3];
			op2.sta[zero-3]=temp2;