#include?
#include?

#define?Line?5
#define?Row?8

int?X1=0?Y1=0?X2=0?Y2=0;
int?Step=0;
bool?Success?=?false;
char?Maze[Line+2][Row+2];

class?Node
{
??public:
????int?x;
????int?y;
????int?s;
????Node?*prior;
????Node?*next;
????Node?*father;
};

class?Queue
{
??public:
????Node?*front;
????Node?*rear;
????Queue（）{front=NULL;?rear=NULL;?};
????~Queue（）{Destory（front）;?front=NULL;?rear=NULL;?};
????bool?IsEmpty（）;
????bool?Destory（Node?*Current）;
????bool?InQueue（int?x?int?y?int?s）;
????bool?OutQueue（）;
????void?NodeTry（int?x?int?y?int?s?Node?*Current）;
????bool?NodeCheck（int?x?int?y?int?s?Node?*Current）;
????bool?FindPath（）;?
};


bool?Queue::InQueue（int?x?int?y?int?s）
{
????Node?*p?=?new?Node;
????p->x?=?x;
????p->y?=?y;
????p->s?=?s;
????p->father?=?front;
????if（IsEmpty（））
????{
????????front?=?p;
????????rear?=?p;
????}
????else
????{
????????rear->next?=?p;
????????rear?=?p;
????}
????return?true;
};


bool?Queue::NodeCheck（int?x?int?y?int?s?Node?*Current）
{
????if（Success）
????{
????????return?true;
????}
????if（IsEmpty（））
????{
????????return?false;
????}
????if（x==X1?&&?y==Y1）
????{
????????Success?=?true;
????????//找到入口點（X1，Y1），打印輸出最短路徑
????????printf（“\n　走出迷宮的最短路徑需要?%d?步：\n\n“?（front->s?+?2））;
????????Maze[X1][Y1]?=?‘A‘;
????????Maze[front->x][front->y]?=?‘A‘;
????????while（front->father!=NULL）
????????{
????????????Maze[front->father->x][front->father->y]?=?‘A‘;
????????????front?=?front->father;
????????}
????????Maze[X2][Y2]?=?‘A‘;
????????return?true;
????}
????else
????{
????????if（Maze[x][y]==‘o‘）
????????{
????????????InQueue（x?y?s）;
????????????Maze[x][y]=‘Y‘;
????????????return?true;
????????}
????????else
????????{
????????????if（Maze[x][y]==‘Y‘）
????????????{
????????????????return?true;
????????????}
????????????else
????????????{
????????????????return?false;
????????????}
????????}
????}??
}

void?Queue::NodeTry（int?x?int?y?int?s?Node?*Current）
{
????NodeCheck（x?y-1?s+1?Current）;
????NodeCheck（x?y+1?s+1?Current）;
????NodeCheck（x-1?y?s+1?Current）;
????NodeCheck（x+1?y?s+1?Current）;
}

bool?Queue::OutQueue（）
{
????if（IsEmpty（））
????{
????????//隊列空！
????????return?false;
????}
????else
????{
????????if（front?!=?rear）
????????{
????????????front?=?front->next;
????????}
????????else
????????{
????????????front=NULL;
????????????rear=NULL;
????????}
????}
????return?true;
}

bool?Queue::FindPath（）
{
????if（!IsEmpty（））
????{
????????NodeTry（front->x?front->y?front->s?front->father）;
????????OutQueue（）;
????????return?true;
????}
????else
????{
????????return?false;
????}
}

bool?Queue::IsEmpty（）
{
????return?（front==NULL?&&?rear==NULL）;
}

bool?Queue::Destory（Node?*Current）
{
????if（Current!=NULL）
????{
????????Destory（Current->next）;
????????delete?Current;
????}
????return?true;
}

int?main（）
{
????int?i?

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

?????文件???????5783??2010-05-21?23:09??maze\“走迷宮”算法，C++源代碼（5×8+矩陣）\“走迷宮”算法.cpp

?????文件???????5891??2010-05-24?23:01??maze\迷宮算法\迷宮算法一.txt

?????文件???????7730??2010-05-24?23:02??maze\迷宮算法\迷宮算法二.txt

?????文件???????4726??2010-05-24?23:02??maze\迷宮算法\迷宮算法三.txt

?????文件???????4236??2010-05-24?23:03??maze\迷宮算法\迷宮算法四.txt

?????目錄??????????0??2011-03-10?16:20??maze\“走迷宮”算法，C++源代碼（5×8+矩陣）

?????目錄??????????0??2011-03-10?16:20??maze\迷宮算法

?????目錄??????????0??2011-03-10?16:20??maze

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

????????????????28366????????????????????8