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

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

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

struct?Map//圖
{
????int?cell[N][N];//數碼數組
????Direction?BelockDirec;//所屏蔽方向
????int?step;
????struct?Map?*?Parent;//父節點
};

//打印圖
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;
????}
????//移動數字
????int?t_i?=?it_j?=?j;
????bool?AbleMove?=?true;
????switch（Direct）//判斷沿direct所指方向移動數字是否被允許
????{
????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）//不可以移動則返回原節點
????{
????????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;
}

//初始化一個初始圖
//由目標圖生成初始圖，保證可以獲得結果
struct?Map?*?RandomMap（const?struct?Map?*?map）
{
????int?M?=?30;//隨機移動圖步數
????struct?Map?*?NewMap;
????NewMap?=?new?Map（）;
????memcpy（NewMapmapsizeof（Map））;?
????srand（（unsigned）time（NULL））;
????for（int?i?=?0;?i?????{????
????????int?Direct?=?rand（）%4;
????????NewMap?=?MoveMap（NewMap（Direction）Directfalse）;
????}
????return?NewMap;
}
//初始圖的另種生成方式，隨機生成各位置的數
//此方式生成的圖在有限次搜索中若深度超過5則多數無解
struct?Map?*?RandomMap（）
{
?int?a[9];
?struct?Map?*?NewMap;
????NewMap?=?new?Map（）;
?srand（（unsigned）time（NULL））;
?for（int?k?=?0;?k?????{??
??bool?Isre?=?false;
??a[k]?=?rand（）%9;
??for?（int?l?=?0;?l???{
???if?（a[k]?==?a[l]）
???{?
????Isre?=?true;
????break;
???}
??}
??if（Isre）
??{
???k?=?k?-?1;
???continue;
??}
?}
????

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

?????文件???????4243??2009-05-04?23:41??DFS\DFS.dsp

?????文件????????531??2009-05-04?17:09??DFS\DFS.dsw

?????文件??????41984??2009-05-11?22:14??DFS\DFS.ncb

?????文件??????53760??2009-05-11?22:14??DFS\DFS.opt

?????文件???????1242??2009-05-11?22:13??DFS\DFS.plg

?????文件???????6251??2009-05-11?22:13??DFS\dfs8.cpp

?????文件?????????33??2009-05-23?22:59??DFS\Readme.txt

?????目錄??????????0??2009-05-24?10:40??DFS

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

???????????????108044????????????????????8