/******************************************************************************
*?使用深度優先、廣度優先和A*算法解決九宮問題
******************************************************************************/

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


#include“data.h“
#include“queue.h“
#include“stack.h“
#include“link.h“


#define?DEEPSEARCH????1????
#define?WIDESEARCH????2????
#define?ASTART????3????????

#define?SEARCHTYPE?WIDESEARCH???//定義使用廣度優先


//#define?SHOWPROCESS????//定義是否顯示中間過程



class?SearchTree?{
private:
	/***********************定義open表的數據類型************************/
#if?SEARCHTYPE==WIDESEARCH
	Queue?open;
#elif?SEARCHTYPE==DEEPSEARCH
	Stack?open;
#else????
	link?open;
#endif


	Stack?close;
public:
	void?init（）;????//初始化數據
	void?extend（）;???????//擴展close表尾節點并添加進open表
	void?moveToClose（）;????//將open表的頭節點移動到close表中
	bool?success（）;????????//判斷搜索是否成功
	bool?openEmpty（）;????//判斷open表是否為空
	void?showAnswer（）;????//顯示最終結果
};

void?SearchTree::showAnswer（）?{
	close.show（）;
}

bool?SearchTree::openEmpty（）?{
	return?open.empty（）;
}


void?SearchTree::extend（）?{
	DATATYPE?temp[LINE][ROW]?buf[LINE][ROW];
	Data?*pid;
	int?n?m;
	pid?=?close.getTop（*buf）;????//將close表的最后一項記錄復制到buf中
	for?（n?=?0;?n		for?（m?=?0;?m			if?（buf[n][m]?==?0）//尋找buf中0所在的位置，0表示空格
				goto?L1;
L1:


	memcpy（temp?buf?DATASIZE?*?sizeof（DATATYPE））;
	if?（n?!=?0）?{????//空格上移
		temp[n][m]?=?temp[n?-?1][m];
		temp[n?-?1][m]?=?0;
		if?（close.exist（*temp）?==?false）?open.push（*temp?&pid）;
#ifdef?SHOWPROCESS????//宏定義，決定時候輸出中間過程
		cout?<		showElement（*temp）;
		getchar（）;
#endif
	}



	memcpy（temp?buf?DATASIZE?*?sizeof（DATATYPE））;
	if?（n?!=?2）?{????//空格下移
		temp[n][m]?=?temp[n?+?1][m];
		temp[n?+?1][m]?=?0;
		if?（close.exist（*temp）?==?false）?open.push（*temp?&pid）;
#ifdef?SHOWPROCESS
		cout?<		showElement（*temp）;
		getchar（）;
#endif
	}

	memcpy（temp?buf?DATASIZE?*?sizeof（DATATYPE））;
	if?（m?!=?0）?{????//空格左移
		temp[n][m]?=?temp[n][m?-?1];
		temp[n][m?-?1]?=?0;
		if?（close.exist（*temp）?==?false）?open.push（*temp?&pid）;
#ifdef?SHOWPROCESS
		cout?<		showElement（*temp）;
		getchar（）;
#endif
	}


	memcpy（temp?buf?DATASIZE?*?sizeof（DATATYPE））;
	if?（m?!=?2）?{????//空格右移
		temp[n][m]?=?temp[n][m?+?1];
		temp[n][m?+?1]?=?0;
		if?（close.exist（*temp）?==?false）?open.push（*temp?&pid）;
#ifdef?SHOWPROCESS
		cout?<		showElement（*temp）;
		getchar（）;
#endif
	}



}

void?SearchTree::moveToClose（）?{
	DATATYPE?dt[DATASIZE];
	Data?*pid;
	open.pop（dt?&pid）;
	close.push（dt?&pid）;
}


bool?SearchTree::success（）?{
	DATATYPE?dt[DATASIZE];
	close.getTop（dt）;
	return?memcmp（dt?*sg?DATASIZE?*?sizeof（DATATYPE））???false?:?true;
}

void?SearchTr

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-03-25?18:12??jiugongge8\
?????目錄???????????0??2018-03-25?17:22??jiugongge8\.vs\
?????目錄???????????0??2018-03-25?17:22??jiugongge8\.vs\jiugongge8\
?????目錄???????????0??2018-03-27?19:36??jiugongge8\.vs\jiugongge8\v15\
?????文件???????38912??2018-03-27?19:36??jiugongge8\.vs\jiugongge8\v15\.suo
?????文件?????4714496??2018-03-27?19:36??jiugongge8\.vs\jiugongge8\v15\Browse.VC.db
?????目錄???????????0??2018-03-25?17:23??jiugongge8\.vs\jiugongge8\v15\ipch\
?????目錄???????????0??2018-03-25?17:23??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\
?????目錄???????????0??2018-03-25?17:33??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\
?????目錄???????????0??2018-03-25?17:23??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\DATA-5979d51e\
?????文件??????327680??2018-03-25?17:31??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\DATA-5979d51e\DATA.ipch
?????目錄???????????0??2018-03-25?17:25??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\link-6cb0be72\
?????文件??????327680??2018-03-25?17:31??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\link-6cb0be72\link.ipch
?????目錄???????????0??2018-03-25?17:33??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\MAIN-d4d68584\
?????文件????23789568??2018-03-27?07:00??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\MAIN-d4d68584\MAIN.ipch
?????目錄???????????0??2018-03-25?17:31??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\QUEUE-9f0ca209\
?????文件??????327680??2018-03-25?17:31??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\QUEUE-9f0ca209\QUEUE.ipch
?????目錄???????????0??2018-03-25?17:32??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\STACK-3659cb9a\
?????文件??????327680??2018-03-25?17:32??jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\STACK-3659cb9a\STACK.ipch
?????目錄???????????0??2018-03-25?17:40??jiugongge8\Debug\
?????文件???????59392??2018-03-25?17:58??jiugongge8\Debug\jiugongge8.exe
?????文件??????468932??2018-03-25?17:58??jiugongge8\Debug\jiugongge8.ilk
?????文件??????667648??2018-03-25?17:58??jiugongge8\Debug\jiugongge8.pdb
?????目錄???????????0??2018-03-25?18:12??jiugongge8\Release\
?????文件???????14848??2018-03-25?18:12??jiugongge8\Release\jiugongge8.exe
?????文件???????66319??2018-03-25?18:12??jiugongge8\Release\jiugongge8.iobj
?????文件???????25408??2018-03-25?18:12??jiugongge8\Release\jiugongge8.ipdb
?????文件??????651264??2018-03-25?18:12??jiugongge8\Release\jiugongge8.pdb
?????目錄???????????0??2018-03-25?18:12??jiugongge8\jiugongge8\
?????目錄???????????0??2018-03-25?17:58??jiugongge8\jiugongge8\Debug\
?????文件????????1057??2018-03-25?17:40??jiugongge8\jiugongge8\Debug\jiugongge8.Build.CppClean.log
............此處省略33個文件信息