#include
?#include?
#include???
struct?node
{??
	int?xy;??
int?cntdif;??
int?step;??
int?f[9];??
int?xy[3][3];?
}queue[10000];???
int?map[3][3];?
?int?dir[4][2]={{-10}{10}{01}{0-1}};?
?int?hash[10000];?
?int?zz[9];
?int?f1f2;??
?struct?node?sourdest;???
?int?judge（int?a[]）????//用逆序數判斷是否可達????
?{??
	?int?ijk=0;?
	?for（i=1;i<9;i++）???
		?if（a[i]）????
			?for（j=0;j				?if（a[j]>a[i]）?????
					?k++;??
				?return?k;?
?}
?int?count（int?a[]int?b[]）??//計算不一樣的個數?
?{??
	?int?ij;??
?for（i=j=0;i<9;i++）??
	?if（a[i]!=b[i]）???
		?j++;??
	?return?j;?
?}?
?int?match（struct?node?m）??//判斷是否和末狀態匹配?
?{??int?ij;????
?for（i=0;i<9;i++）?????
	?if（m.f[i]!=zz[i]）
		?return?0;???
	?return?1;???
?}????
?
int?comp（const?void?*pconst?void?*q）
{
	?struct?node?*a=（struct?node?*）p;???
	?struct?node?*b=（struct?node?*）q;?
	if（a->cntdif==b->cntdif）???
		return?a->step-b->step;??
	return?a->cntdif-b->cntdif;?
?}
int?visit（int?x[]）//返回hash函數值?
{???
	int?icnt=1sum=0;???
	for（i=0;i<9;i++）?????
		sum+=x[i]*cnt++;???
	return?sum;?
?}?

void?print（int?f[][3]）??
{????
	int?ij;???
	for（i=0;i<3;i++）???
	{?????
		for（j=0;j<3;j++）???
			printf（“%d?“f[i][j]）;????
		printf（“\n“）;
		}????
	printf（“\n“）;??
}
???void?bfs（）//廣搜
{????
	???int?pvalijff[9]flin=0;???
	???int?head=0;???
	???int?tail=0;?
??memset（queue0sizeof（queue））;???
??queue[head]=sour;?????
??queue[head].cntdif=count（queue[head].fzz）;??
??hash[head]=visit（queue[head].f）;??
??print（queue[head].xy）;//打印頭結點
??while（head<=tail）??
??{??
	??struct?node?HH=queue[head++];??
	??int?sxsy;??
	??for（p=0;p<4;p++）??
	??{
		??flin=0;??????
		??for（i=0;i<9;i++）//把頭結點的值賦在此?????
			??ff[i]=HH.f[i];????
		??sx=HH.x+di