//?DNF_Search.cpp?:?Defines?the?entry?point?for?the?console?application.
//


#include?“iostream.h“
#include?“stdio.h“
#include?“stdlib.h“
#include?“string.h“
#include?
#include?
using?namespace?std;

const?int?N?=?3;//3*3圖
enum?Direction{NoneUpDownLeftRight};//方向

struct?Map?//存儲數(shù)組及方向信息
{
????int?cell[N][N];??//數(shù)碼數(shù)組
????Direction?BelockDirec;//所屏蔽方向
????int?step;
????struct?Map?*?Parent;//父節(jié)點
};

//打印圖
void?PrintMap（struct?Map?*map）
{
????cout<<“*************************************************“<????for（int?i=0;i????{
????????for（int?j=0;j????????{
??????????cout<cell[i][j]<<“???“;
????????}
????????cout<????}
?cout<<“*************************************************“<}
//移動圖
struct?Map?*?MoveMap（struct?Map?*?mapDirection?Directbool?CreateNewMap）
{
????struct?Map?*?NewMap;

????//獲取空閑格位置
????int?ij;
????for（i?=?0;?i?????{
????????bool?HasGetBlankCell?=?false;
????????for（j?=?0;?j?????????{
????????????if（map->cell[i][j]?==?0）
????????????{
????????????????HasGetBlankCell?=?true;
????????????????break;
????????????}
????????}
????????if（HasGetBlankCell）
????????????break;
????}
????//移動數(shù)字
????int?t_i?=?it_j?=?j;
????bool?AbleMove?=?true;
????switch（Direct）????//判斷沿direct所指方向移動數(shù)字是否被允許
????{
		case?Down:
			t_i++;
			if（t_i?>=?N）
			?AbleMove=false;
			break;
		case?Up:
			t_i--;
			if（t_i?				AbleMove=false;
			break;
		case?Left:
			t_j--;
			if（t_j?				AbleMove=false;
			break;
		case?Right:
			t_j++;
			if（t_j?>=?N）
				AbleMove=false;
			break;
????};

????if（!AbleMove）//不可以移動則返回原節(jié)點
????{
????????return?map;
????}

????if（CreateNewMap）
????{
????????NewMap?=?new?Map（）;
????????for（int?x?=?0;?x?????????????for（int?y?=?0;?y?????????????????NewMap->cell[x][y]?=?map->cell[x][y];
????}
????else?NewMap?=?map;
????NewMap->cell[i][j]?=?NewMap->cell[t_i][t_j];
????NewMap->cell[t_i][t_j]?=?0;

????return?NewMap;
}


//判斷是否搜索到目標狀態(tài)
bool?IsSuccess（struct?Map?*?mapstruct?Map?*?Target）
{
????bool?IsSuc?=?true;
????for（int?i?=?0;?i?????{
????????for（int?j?=?0;?j?????????{
????????????if（map->cell[i][j]?!=?Target->cell[i][j]）
			{
??????????????IsSuc?=?false;
??????????????break;
			}
????????}
????????if（!IsSuc）
?????????break;
????}
????return?IsSuc;
}

struct?Map?*?DNF_Search（struct?Map?*?beginstruct?Map?*?Targetint?dm）
{
	struct?Map?*?p1?*p2*T=NULL;
	int?step=1;
	stack??OPEN;
	stack??CLOSED;
	OPEN.push（begin）;
	do
	{
		p1=OPEN.top（）;
		cout?<			PrintMap（p1）;
		OPEN.pop（）;
		if（IsSuccess（p1Target））
		{
			T=p1;
			return?T;
		}
		if（p1->step==dm）
		{
			CLOSED.push（p1）;
			continue;
		}
		for?（int?i?=?1;?i?<=?4;?i++）
		{
			Direction?Direct?=?（Direction）?i;
			if（Direct?==?p1->BelockDirec）//跳過屏蔽方向
				continue;
			p2?=?Mov

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

?????文件???????1080??2010-01-16?10:04??EiNum\Debug\1.obj

?????文件??????48589??2010-01-16?10:43??EiNum\Debug\dfs8.obj

?????文件?????221225??2010-01-16?10:58??EiNum\Debug\EiNum.exe

?????文件?????274020??2010-01-16?10:58??EiNum\Debug\EiNum.ilk

?????文件??????48574??2010-01-16?10:58??EiNum\Debug\EiNum.obj

?????文件?????186920??2010-01-16?09:50??EiNum\Debug\EiNum.pch

?????文件????1098752??2010-01-16?10:58??EiNum\Debug\EiNum.pdb

?????文件???????1080??2010-01-16?09:50??EiNum\Debug\Text2.obj

?????文件?????214016??2010-01-16?10:58??EiNum\Debug\vc60.idb

?????文件?????176128??2010-01-16?10:58??EiNum\Debug\vc60.pdb

?????文件???????4324??2010-01-16?11:08??EiNum\EiNum.cpp

?????文件???????4266??2010-01-16?11:00??EiNum\EiNum.dsp

?????文件????????516??2010-01-16?09:43??EiNum\EiNum.dsw

?????文件??????41984??2010-01-16?11:08??EiNum\EiNum.ncb

?????文件??????48640??2010-01-16?11:08??EiNum\EiNum.opt

?????文件???????1228??2010-01-16?10:59??EiNum\EiNum.plg

?????文件??????57344??2010-01-16?10:59??EiNum\Release\EiNum.exe

?????文件??????13321??2010-01-16?10:59??EiNum\Release\EiNum.obj

?????文件????2128192??2010-01-16?10:59??EiNum\Release\EiNum.pch

?????文件??????33792??2010-01-16?10:59??EiNum\Release\vc60.idb

?????目錄??????????0??2010-01-16?10:58??EiNum\Debug

?????目錄??????????0??2010-01-16?10:59??EiNum\Release

?????目錄??????????0??2010-01-16?11:08??EiNum

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

??????????????4603991????????????????????23