/*寬度優(yōu)先算法中，我定義了一個(gè)狀態(tài)結(jié)構(gòu)來描述每個(gè)狀態(tài)，用一個(gè)數(shù)組來存放操作符，用continue來判斷可否進(jìn)行某些操作。根據(jù)寬度優(yōu)先算法搜索出
到達(dá)目標(biāo)狀態(tài)的路徑。路徑用一個(gè)數(shù)組來存儲(chǔ)，輸出時(shí)用逆序輸出，即為正序結(jié)果。*/

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

struct?Snode		//表結(jié)構(gòu)
{
	int?parent;??//父節(jié)點(diǎn)的編號(hào)
	int?current[9];	//當(dāng)前節(jié)點(diǎn)
public:
	void?TransformIn（const?int?*d）;//更換當(dāng)前節(jié)點(diǎn)
};


Snode?OPEN[50000];
int?op?=?0;//OPEN表中的個(gè)數(shù)
Snode?CLOSE[50000];
int?cp?=?0;//CLOSED表中的個(gè)數(shù)
int?result[50000][9];???//result數(shù)組用于保存路徑


void?Snode::TransformIn（const?int?*d）
{
????for（int?i=0;i<9;++i）
		current[i]=d[i];
}

int?have_exist（Snode?&node1Snode?&node2）???????????????????????????????????????//判斷是否已存在該節(jié)點(diǎn)
{
	int?flag=1;
	for（int?i=0;i<9;i++）
	{
		if（node1.current[i]!=node2.current[i]）?flag=0;
	}
	return?flag;
}

inline?void?swapn（int?&aint?&b）
{
	int?tmp=a;
????a=b;
????b=tmp;
}

int?judge（Snode?&node）?????????????????????????????????????????????????????????//判斷節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)
{
	int?flag=1;
	int?g[9]={123804765};
	for（int?i=0;i<9;i++）
	{
		if（node.current[i]!=g[i]）
			flag=0;
	}
	return?flag;
}

int?Astar（const?int?*d）???????????????????????????????????????????????????????//深度優(yōu)先算法實(shí)現(xiàn)
{
	int?step?=?0;
	int?begin=0;????????????????????//當(dāng)前擴(kuò)展的節(jié)點(diǎn)
	int?node_number=1;??????????????//生成狀態(tài)總數(shù)
	static?int?dp[4]={-3-113};???//移動(dòng)操作符：上、左、右、下
????op=1;
????cp=0;
????OPEN[begin].TransformIn（d）;
	OPEN[begin].parent=-1;//根節(jié)點(diǎn)的parent為-1
????while（op>0）//OPEN表不為空
	{
		int?i=0zeroposj=0k=0;

		/////////////////////////////////////找到目標(biāo)節(jié)點(diǎn)->輸出路徑
????????if（judge（OPEN[begin]）==1）??
		{
			CLOSE[cp]=OPEN[begin];	//被擴(kuò)展的節(jié)點(diǎn)放入CLOSED表中
			while（begin!=-1）?????????//記錄路徑
			{
???????????????for（int?i=0;i<9;i++）
			???{
				???result[j][i]=OPEN[begin].current[i];
			???}
			???j=j+1;
			???begin=OPEN[begin].parent;
			}
			for（i=j-1;i>=0;i--）//正序輸出路徑
			{
				cout?<				for（k=0;k<9;k++）
				{
					cout<					
				????if（k%3==2）??cout<				}
				cout?<				cout<