#include?“StdAfx.h“
#include?“BfsDfs.h“

CBfsDfs::CBfsDfs（void）
{
}

CBfsDfs::~CBfsDfs（void）
{
		delete?beg;						//解決內存泄露的問題！
		while（!m_Queue.empty（））
		{
			map?*inter=m_Queue.front（）;
			m_Queue.pop（）;
			delete?inter;
		}
}


CBfsDfs::CBfsDfs（int?*pointint?*goal）
{
	numStep?=?0;
	beg?=?new?map;
	for?（int?n=0;n	{
		beg->dig[n]?=?*（point+n）;
		end.dig[n]?=?*（goal+n）;
	}
	beg->last?=?NULL;
	beg->lockDir?=?None;

	beg->layer?=?0;
}
bool?CBfsDfs::Judge（）
{
	int?a1=numDes（&end）;
	int?a2=numDes（beg）;
	if（a1!=a2）?return?0;
	if?（CheckRepeat（beg））?return?0;
	if?（CheckRepeat（&end））?return?0;
	return?1;
}

void?CBfsDfs::Cal（bool?BorD）
{

		double?startTime=clock（）;				//設計計時器，計算所用過的時間

		if?（0?==?BorD）
		{
			T=BNFS（beg&end）;
		}?
		else
		{
			T=DNFS（beg&end）;
		}

		double?endTime=clock（）;

		if（T?!=?NULL）
		{
			map?*p=T;
			stack?Stack1;
			while（p->last?!=?NULL）			//將所有的數據壓入堆棧，一個一個彈出顯示
			{
				Stack1.push（p）;
				p=p->last;
			}
			while（!Stack1.empty（））
			{
				numStep++;
				Stack1.pop（）;
			}
			caltime?=?endTime-startTime;			
		}

}

map?*?CBfsDfs::Move（map?*Map?dir?Direct?bool?CreateNewMap）
{
	map?*?NewMap;?
	//獲取空閑格位置
	int?i;
	for（i=0;i		if（Map->dig[i]==0）
			break;
	//移動數字
	int?j=i;				//j記錄了0的原始位置，i記錄了0換后的位置
	bool?AbleMove?=?true;
	switch（Direct）
	{????
	case?Up:??
		if（i<3）
			AbleMove=false;
		i=i+add[0];
		break;
	case?Down:??
		if（i>5）
			AbleMove=false;
		i=i+add[1];
		break;
	case?Left:??
		if（i%3==0）
			AbleMove=false;
		i=i+add[2];
		break;
	case?Right:??
		if（i%3==2）
			AbleMove=false;
		i=i+add[3];
		break;
	};
	if（!AbleMove）//不可以移動則返回原節點
		return?Map;
	if（CreateNewMap）			//創建一個新的節點
	{
		NewMap=?new?map（）;

		m_Queue.push（NewMap）;

		for（int?x=0;x		{
			NewMap->dig[x]=Map->dig[x];
		}
	}
	else
		NewMap?=?Map;
	NewMap->dig[j]?=?NewMap->dig[i];
	NewMap->dig[i]=0;
	return?NewMap;
}

bool?CBfsDfs::ifSuccess（map?*Map?map?*end）
{
	bool?suc?=?true;
	for（int?i=0;i	{
		if（Map->dig[i]!=end->dig[i]）
		{
			suc?=?false;
			break;
		}
	}
	return?suc;
}

map?*?CBfsDfs::BNFS（map?*?begmap?*?end）
{
	map?*?p1?*p2?*p=NULL;
	bool?IsSucc?=?false;
	queue?Queue;					//創建一個隊列，并指定放入隊列的類型
	if（ifSuccess（begend））
		return?beg;
	Queue.push（beg）;					//放入隊列中
	do
	{
		p1?=?Queue.front（）;
		Queue.pop（）;
		for?（int?i?=?0;?i?		{
			dir?Direct=（dir）i;
			if（Direct==p1->lockDir）		//自己原來錯了，這里沒能理解continue的用法，continue表示：不進行這次循環，而直接進行下一次的循環
				continue;
			p2?=?Move（p1Directtrue）;
			if（p2?!=?p1）//數碼是否可以移動
			{?
				p2->last?=?p1;
				switch（Direct）//設置屏蔽方向
				{
				case?Up:
					p2->lockDir?=?Down;			//記錄父節點的操作，防止又回到原狀態，又走回去
					break;
				case?Down:
					p2->lockDir?=?Up;
					break;
				case?Left:
					p2->lockDir?=?Right;
					break;
				case?Right:
					p2->lockDir?=?Left;
					break;
				}

				p2->layer?=?p1->la

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????5127??2010-09-16?15:36??EightPuzzle\EightPuzzle\BfsDfs.cpp

?????文件???????1413??2010-09-16?14:50??EightPuzzle\EightPuzzle\BfsDfs.h

?????文件??????61684??2010-09-16?15:12??EightPuzzle\EightPuzzle\EightPuzzle.aps

?????文件???????1714??2010-09-14?19:04??EightPuzzle\EightPuzzle\EightPuzzle.cpp

?????文件????????471??2010-09-14?19:04??EightPuzzle\EightPuzzle\EightPuzzle.h

?????文件??????14655??2010-09-16?15:12??EightPuzzle\EightPuzzle\EightPuzzle.rc

?????文件???????5635??2010-09-14?19:42??EightPuzzle\EightPuzzle\EightPuzzle.vcproj

?????文件???????1425??2010-09-16?15:36??EightPuzzle\EightPuzzle\EightPuzzle.vcproj.yangtianzhi-PC.yangtianzhi.user

?????文件???????6803??2010-09-16?15:25??EightPuzzle\EightPuzzle\EightPuzzleDlg.cpp

?????文件???????1184??2010-09-16?15:25??EightPuzzle\EightPuzzle\EightPuzzleDlg.h

?????文件???????2835??2010-09-14?19:04??EightPuzzle\EightPuzzle\ReadMe.txt

?????文件??????21630??2005-12-08?14:56??EightPuzzle\EightPuzzle\res\EightPuzzle.ico

?????文件????????367??2010-09-14?19:04??EightPuzzle\EightPuzzle\res\EightPuzzle.rc2

?????文件???????1741??2010-09-16?15:12??EightPuzzle\EightPuzzle\resource.h

?????文件????????142??2010-09-14?19:04??EightPuzzle\EightPuzzle\stdafx.cpp

?????文件???????2489??2010-09-14?19:04??EightPuzzle\EightPuzzle\stdafx.h

?????文件????????898??2010-09-14?19:04??EightPuzzle\EightPuzzle.sln

????..A..H.?????15360??2010-09-16?15:36??EightPuzzle\EightPuzzle.suo

?????目錄??????????0??2010-09-14?19:04??EightPuzzle\EightPuzzle\res

?????目錄??????????0??2010-09-16?15:37??EightPuzzle\EightPuzzle

?????目錄??????????0??2010-09-16?15:37??EightPuzzle

-----------?---------??----------?-----??----

???????????????145573????????????????????21