/*寬度優先算法中，我定義了一個狀態結構來描述每個狀態，用一個數組來存放操作符，用continue來判斷可否進行某些操作。根據寬度優先算法搜索出
到達目標狀態的路徑。路徑用一個數組來存儲，輸出時用逆序輸出，即為正序結果。*/

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

struct?Snode		//表結構
{
	int?parent;??//父節點的編號
	int?current[9];	//當前節點
public:
	void?TransformIn（const?int?*d）;//更換當前節點
};


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


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

int?have_exist（Snode?&node1Snode?&node2）???????????????????????????????????????//判斷是否已存在該節點
{
	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）?????????????????????????????????????????????????????????//判斷節點是否為目標節點
{
	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）???????????????????????????????????????????????????????//深度優先算法實現
{
	int?step?=?0;
	int?begin=0;????????????????????//當前擴展的節點
	int?node_number=1;??????????????//生成狀態總數
	static?int?dp[4]={-3-113};???//移動操作符：上、左、右、下
????op=1;
????cp=0;
????OPEN[begin].TransformIn（d）;
	OPEN[begin].parent=-1;//根節點的parent為-1
????while（op>0）//OPEN表不為空
	{
		int?i=0zeroposj=0k=0;

		/////////////////////////////////////找到目標節點->輸出路徑
????????if（judge（OPEN[begin]）==1）??
		{
			CLOSE[cp]=OPEN[begin];	//被擴展的節點放入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<