?#include“stdio.h“
?#include“malloc.h“?
?#include“stdlib.h“?
?#define?TRUE?1
?#define?FALSE?0
?#define?OK?1
?#define?ERROR?0
?#define?INFEASIBLE?-1
?typedef?int?Status;


?typedef?struct?/*?迷宮坐標位置類型?*/
?{
???int?x;?/*?行值?*/
???int?y;?/*?列值?*/
?}PosType;
typedef?int?MazeType[10][10];?/*?迷宮數組[行][列]?*/

?MazeType?m;?/*?迷宮數組?全局變量處理?因為我在初始化的時候老是弄出毛病*/
?int?curstep=1;?/*?當前足跡是第幾個初值為1?*/

?typedef?struct?/*?棧的元素類型?*/
?{
???int?ord;?/*?通道塊在路徑上的＂序號＂?*/
???PosType?seat;?/*?通道塊在迷宮中的＂坐標位置＂?*/
???int?di;?/*?從此通道塊走向下一通道塊的＂方向＂（0～3表示東～北）?*/
?}SElemType;

?#include“Stack.h“

/*此處因為在Stack.h中用到了SElemeType?所以在此處導入stack.h?*/

?/*?定義墻元素值為0可通過路徑為1不能通過路徑為-1通過路徑為足跡記錄為*?*/





void?mazeprint（）
?{?/*?輸出迷宮的解?*/
???int?ij;
???for（i=0;i<10;i++）
??{
	??for（j=0;j<10;j++）
	??{
		??if（m[i][j]==（int）?“*“）//輸出時如果是*?則輸出*
		????printf（“??*“）;
		??else{	??
		??printf（“?%2d“m[i][j]）;
		??if（j==9）
			??printf（“\n“）;
		??}
	??}
??}	??
?}





?Status?Pass（PosType?b）
?{?/*?當迷宮m的b點的序號為1（可通過路徑），return?OK;?否則，return?ERROR。?*/


???if（m[b.x][b.y]==1）
?????return?OK;
???else
?????return?ERROR;
?}

?void?FootPrint（PosType?a）
?{?/*?使迷宮m的a點的序號變為足跡（curstep）?*/
???m[a.x][a.y]=（int）?“*“;
?}

?PosType?NextPos（PosType?cint?di）
?{?/*?根據當前位置及移動方向，返回下一位置?*/
???PosType?direc[4]={{01}{10}{0-1}{-10}};?/*?{行增量列增量}?*/
???/*?移動方向依次為東南西北?*/
???c.x+=direc[di].x;
???c.y+=direc[di].y;
???return?c;
?}

?void?MarkPrint（PosType?b）
?{?/*?使迷宮m的b點的序號變為-1（不能通過的路徑）?*/
???m[b.x][b.y]=-1;
?}

?Status?MazePath（PosType?startPosType?end）?
?{?/*?若迷宮maze中存在從入口start到出口end的通道，則求得一條?*/
???/*?存放在棧中（從棧底到棧頂），并返回TRUE；否則返回FALSE?*/
???SqStack?S;
???PosType?curpos;
???SElemType?e;
???InitStack（&S）;
???curpos=start;
???

???do
???{
?????if（Pass（curpos））/*?當前位置可以通過，即是未曾走到過的通道塊?*/
?????{?
???????FootPrint（curpos）;?/*?留下足跡?*/
???????e.ord=curstep;
???????e.seat.x=curpos.x;
???????e.seat.y=curpos.y;
???????e.di=0;
???????Push（&Se）;?/*?入棧當前位置及狀態?*/
???????curstep++;?/*?足跡加1?*/
???????if（curpos.x==end.x&&curpos.y==end.y）?/*?到達終點（出口）?*/
?????????return?TRUE;
???????curpos=NextPos（curpose.di）;
?????}
?????else
?????{?/*?當前位置不能通過?*/
???????if（!StackEmpty（S））
???????{
?????????Pop（&S&e）;?/*?刪除棧頂元素???并用e帶回基本信息*/
?????????curstep--;
?????????while（e.di==3&&!StackEmpty（S））?/*?前一位置處于最后一個方向（北）?即所有方向都無法通過了*/
?????????{
???????????MarkPrint（e.seat）;?/*?留下不能通過的標記（-1）?*/
???????????Pop（&S&e）;?/*?退回一步?*/
???????????curstep--;
?????????}
?????????if（e.di<3）?/*?沒到最后一個方向（北）?*/
?????????{
???????????e.di++;?/*?換下一個方向探索?*/
???????????Push（&Se）;
???????????curstep++;
???????????curpos=NextPos（e.seate.di）;?/*?設定當前位置是該新方向上的相鄰塊?*/
?????????}
???????}
?????}
???}while（!StackEmpty（S））;
???return?FALSE;
?}

?void?main（）
?{
???PosType?beginend;
???int?ij;

??MazeType?newm={???
	???{0000000000}
	???{0110111010}
	???{0110011110}
	???{0111110110}
	???{000000

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

?????文件???????2217??2008-12-16?16:48??迷宮問題\Stack.h

?????文件???????4066??2008-12-16?17:16??迷宮問題\mazepath.c

?????目錄??????????0??2008-12-16?16:48??迷宮問題

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

?????????????????6283????????????????????3