#include?
#include?
#include?

typedef?struct?Node
{//節點結構體
????int?data[9];
	double?fg;
	struct?Node?*?parent;
}Node*Lnode;

typedef?struct?Stack
{//OPEN?CLOSED?表結構體
	Node?*?npoint;
	struct?Stack?*?next;
}Stack*?Lstack;

Node?*?Minf（Lstack?*?Open）
{//選取OPEN表上f值最小的節點，返回該節點地址
	Lstack?temp?=?（*Open）->nextmin?=?（*Open）->nextminp?=?（*Open）;
	Node?*?minx;
????while（temp->next?!=?NULL）
	{
		if（（temp->next?->npoint->f）?npoint->f））
		{
			min?=?temp->next;
			minp?=?temp;
		}
		temp?=?temp->next;
	}
	minx?=?min->npoint;
	temp?=?minp->next;
	minp->next?=?minp->next->next;
	free（temp）;
	return?minx;
}

int?Canslove（Node?*?suc?Node?*?goal）
{//判斷是否可解
	int?a?=?0b?=?0ij;
	for（i?=?1;?i		for（j?=?0;j?		{
			if（（suc->data[i]?>?suc->data[j]）?&&?suc->data[j]?!=?0）a++;
			if（（goal->data[i]?>?goal->data[j]）?&&?goal->data[j]?!=?0）b++;
		}
	if（a%2?==?b%2）return?1;
	else?return?0;
}

int?Equal（Node?*?sucNode?*?goal）
{//判斷節點是否相等?，1相等，0不相等
	for（int?i?=?0;?i?		if（suc->data[i]?!=?goal->data[i]）return?0;
????return?1;
}

Node?*?Belong（Node?*?sucLstack?*?list）
{//判斷節點是否屬于OPEN表?或?CLOSED表，是則返回節點地址，否則返回空地址
	Lstack?temp?=?（*list）?->?next?;
	if（temp?==?NULL）return?NULL;
	while（temp?!=?NULL）
	{
		if（Equal（suctemp->npoint））return?temp?->?npoint;
		temp?=?temp->next;
	}
	return?NULL;
}

void?Putinto（Node?*?sucLstack?*?list）
{//把節點放入OPEN?或CLOSED?表中
????Stack?*?temp;
	temp?=（Stack?*）?malloc（sizeof（Stack））;
	temp->npoint?=?suc;
	temp->next?=?（*list）->next;
	（*list）->next?=?temp;
}

///////////////計算f值部分-開始//////////////////////////////
double?Fvalue（Node?suc?Node?goal?float?speed）
{//計算f值
	double?Distance（NodeNodeint）;
	double?h?=?0;
	for（int?i?=?1;?i?<=?8;?i++）
		h?=?h?+?Distance（suc?goal?i）;
	return?h*speed?+?suc.g;?//f?=?h?+?g;（speed值增加時搜索過程以找到目標為優先因此可能不會返回最優解）???????????????????????????????????????
}

double?Distance（Node?suc?Node?goal?int?i）
{//計算方格的錯位距離
	int?kh1h2;
	for（k?=?0;?k?	{
		if（suc.data[k]?==?i）h1?=?k;
		if（goal.data[k]?==?i）h2?=?k;
	}
	return?double（fabs（h1/3?-?h2/3）?+?fabs（h1%3?-?h2%3））;
}
///////////////計算f值部分-結束//////////////////////////////

///////////////////////擴展后繼節點部分的函數-開始/////////////////
int?BelongProgram（Lnode?*?suc?Lstack?*?Open?Lstack?*?Closed?Node?goal?float?speed）
{//判斷子節點是否屬于OPEN或CLOSED表?并作出相應的處理
	Node?*?temp?=?NULL;
	int?flag?=?0;
	if（（Belong（*sucOpen）?!=?NULL）?||?（Belong（*sucClosed）?!=?NULL））
	{
		if（Belong（*sucOpen）?!=?NULL）?temp?=?Belong（*sucOpen）;
		else?temp?=?Belong（*sucClosed）;
		if（（（*suc）->g）?g））
		{
			temp->parent?=?（*suc）->parent;
			temp->g?=?（*suc）->g;
			temp->f?=?（*suc）->f;
		????flag?=?1;
		}
	}
	else
	{
		Putinto（*?suc?Open）;
		（*suc）->f?=?Fvalue（**suc?goal?speed）;
	}
	return?flag;?
}

int?Canspread（Node?suc?int?n）
{//判斷空格可否向該方向移動1，2，3，4表示空格向上向下向左向右移
	int?iflag?=?0;
	for（i?=?0;i?