用深度优先、广度优先算法解决八数码问题

网上大部分解决8数码问题都只采用宽度优先算法。我在宽度优先的基础上，设计出深度优先算法。并制作出界面，方便输入、输出。希望能对学习相关内容的同志有所帮助

#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 < 4; 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