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

typedef?int?map[3][3];

map?start?=?{2??8??3??1??6??4??7??0??5};
map?target?=?{1??2??3??8??0??4??7??6??5};
//**************************************************************
struct?linkN;

typedef?struct?Node
{
	map?data;
	struct?Node?*parent;
	struct?linkN?*child;
	struct?Node?*next;
	int?f_x;
	int?g_x;
	int?h_x;
}NNode??*PNode;

typedef?struct?linkN
{
	struct?linkN?*next;
	struct?Node?*pointData;
}Nlink??*PNlink;

PNode?open;
PNode?closed;

//********************************************************************


void?initlink（PNode?&Head）
{
	Head?=?（PNode）malloc（sizeof（NNode））;
	Head->next?=?NULL;
}
//********************************************************************
bool?isEmpty（PNode?Head）
{
	if（Head->next?==?NULL）
		return?true;
	else
		return?false;
}
//********************************************************************
void?popNode（PNode?&Head??PNode?&FNode）
{
	if（isEmpty（Head））
	{
		FNode?=?NULL;
		return;
	}
	FNode?=?Head->next;
	Head->next?=?Head->next->next;
	FNode->next?=?NULL;
}
//********************************************************************
void?addSpringNode（PNode?&Head??PNode?newData）
{
	PNlink?newNode?=?（PNlink）malloc（sizeof（Nlink））;
	newNode->pointData?=?newData;
	newNode->next?=?Head->child;
	Head->child?=?newNode;
}
//********************************************************************
void?freeSpringlink（PNlink?&Head）
{
	PNlink?t;
	while（Head?!=?NULL）
	{
		t=?Head;
		Head?=?Head->next;
		free（t）;
	}
}
//********************************************************************
void?freelink（PNode?&Head）
{
	PNode?t;

	t?=?Head;
	Head?=?Head->next;
	free（t）;

	while（Head?!=?NULL）
	{
		freeSpringlink（Head->child）;
		t=?Head;
		Head?=?Head->next;
		free（t）;
	}
}
//********************************************************************
void?addNode（PNode?&Head??PNode?&newNode）
{
	newNode->next?=?Head->next;
	Head->next?=?newNode;
}
//********************************************************************
void?addAscNode（PNode?&Head??PNode?&newNode）
{
	PNode?P;
	PNode?Q;

	P?=?Head->next;
	Q?=?Head;
	while（P?!=?NULL?&&?P->f_x?f_x）
	{
		Q?=?P;
		P?=?P->next;
	}
	newNode->next?=?Q->next;
	Q->next?=?newNode;
}
//********************************************************************
int?computeHValue（PNode?theNode）
{
	int?num?=?0;

	for（int?i?=?0?;?i?	{
		for（int?j?=?0?;?j?		{
			if（theNode->data[i][j]?!=?target[i][j]）
				num++;
		}
	}
	return?num;
}
//********************************************************************

void?computeAllValue（PNode?&theNode??PNode?parentNode）
{
	if（parentNode?==?NULL）
		theNode->g_x?=?0;
	else
		theNode->g_x?=?parentNode->g_x?+?1;

	theNode->h_x?=?computeHValue（theNode）;
	theNode->f_x?=?theNode->g_x?+?theNode->h_x;
}

//**********