#include?
#include?
#include?
#define?ok?1
#define?error?0
#define?true??1
#define?false?0
#define?maxrow?10????????????????//最大行數
#define?maxrank?10???????????????//最大列數
#define?stack_max_size?100???????//棧的最大長度
#define?stackincrement?10????????//棧的增加長度

typedef?struct?postype{?????????//迷宮坐標
	int?y;??????????????????????//縱坐標
	int?x;??????????????????????//橫坐標
}postype;?

typedef?struct?way{?????//通道塊儲存結構
	int?ord;?????????????//通道塊在“路徑”上的序號
	postype?seat;????????//通道快在迷宮中的“坐標位置”
	int?di;??????????????//從此通道塊走向下一個通道塊的“方向”
}way;????????????????????//棧的元素結構

typedef?struct?stack{??????//棧結構
	struct?way?*top;?????????//棧頂指針
	struct?way?*base;????????//棧底指針
	int?stacksize;??????????//棧的總長度
}stack;

int?maze[maxrow][maxrank];????//迷宮數組內容為1表示障礙，0表示通路，2表示走過足跡

int?initmaze（postype?*s1postype?*s2）
//構建迷宮函數
{
	int?ij;
	printf（“迷宮為10行10列，請構造迷宮版圖（0為通路，1為障礙）：\n“）;
	for（i=0;i<10;i++）
	{
		printf（“\n請輸入迷宮第%d行構造：\n“i+1）;
		j=0;
		while（j<10）???
		{
			scanf（“%d“&maze[i][j]）;
		????j++;
		}//while
	}
	printf（“請輸入起始坐標（如：2_3）：“）;
	scanf（“%d%d“&s1->x&s1->y）;
	getchar（）;
	printf（“請輸入終點坐標（如：2_3）:“）;
	scanf（“%d%d“&s2->x&s2->y）;
	getchar（）;
	printf（“\n迷宮構造完成！\n“）;
	return?ok;
}
	
int?initstack（stack?*s）
//構建一個空棧
{
	s->base=（way*）malloc（stack_max_size*sizeof（way））;
	if（!s->base）???exit（error）;
	s->top=s->base;
	s->stacksize=stack_max_size;
	return?ok;
}

int?push（stack?*sway?e）
//將e數據入棧
{
	way?*newbase;
	if（s->top-s->base==s->stacksize）????????????????????//若棧滿則增加空間
????{
		newbase=（way*）realloc（s->base（s->stacksize+stackincrement）*sizeof（way））;
		if（!newbase）??exit（error）;
		s->base=newbase;
		s->top=s->base+s->stacksize;
		s->stacksize+=stackincrement;
	}
	*s->top++=e;
	return?ok;
}

int?pop（stack?*sway?*e）
//若棧不為空，則將棧頂元素出棧并保存到e中
{
	if（s->base==s->top）??return?error;???????//棧為空錯誤
	*e=*--s->top;
	return?ok;
}

int?pass（postype?e）
//判斷通道塊e是否可行，若可行返回ok，不可行返回error
{
	if（maze[e.x][e.y]==0）???return?ok;
	else?return?error;
}

int?nextpos（postype?*sint?di）
//探索下一個通道塊坐標，s1為現在坐標，s2返回下一步坐標，di為方向
{
	if（di==1）??s->x++;
	if（di==2）??s->y++;
	if（di==3）??s->x--;
	if（di==4）??s->y--;
????return?ok;
}

int?stackempty（stack?*s）
//判斷棧s是否為空，空返回0，不空返回1
{
	if（s->base==s->top）??return?0;
	else?return?1;
}

int?mazepath（stack?*spostype?startpostype?end）
//迷宮求解函數，start為起始坐標，end為終點坐標
{
	way?e;
	postype?curpos;?????//當前位置
	int?curstep=1;??????//探索第一步
	curpos=start;???????//設置當前位置為起始位置
	if（!initstack（s））??exit（error）;????
	do
	{
		if（pass（curpos））
		{
			maze[curpos.x][curpos.y]=2;??????//留下通過足跡
			e.di=1;
			e.ord=curstep;
			e.seat=curpos;
			push（se）;
			if（curpos.x==end.x&&curpos.y==end.y）??return?true;????//結束
			nextpos（&curpos1）;
			curstep++;
		}//if
		else
		{
			pop（s&e）;
			while（e.di==4&&stackempty（s））??pop（s&e）;
			if（e.di<4）
			{
				e.di++;
				curpos=e.seat;
????????????????nextpos（&curpose

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2011-01-20?08:57??迷宮求解\
?????目錄???????????0??2011-01-20?08:57??迷宮求解\Debug\
?????文件???????33792??2011-04-24?14:04??迷宮求解\Debug\vc60.idb
?????文件???????53248??2011-04-24?14:04??迷宮求解\Debug\vc60.pdb
?????文件??????184378??2011-04-24?14:04??迷宮求解\Debug\迷宮求解.exe
?????文件??????213924??2011-04-24?14:04??迷宮求解\Debug\迷宮求解.ilk
?????文件???????10351??2011-04-24?14:04??迷宮求解\Debug\迷宮求解.obj
?????文件???????43520??2011-04-24?13:43??迷宮求解\Debug\迷宮求解.opt
?????文件??????186652??2011-04-24?10:03??迷宮求解\Debug\迷宮求解.pch
?????文件??????451584??2011-04-24?14:04??迷宮求解\Debug\迷宮求解.pdb
?????文件????????3743??2011-04-24?14:08??迷宮求解\迷宮求解.c
?????文件????????3425??2011-04-24?12:39??迷宮求解\迷宮求解.dsp
?????文件?????????524??2011-04-24?14:08??迷宮求解\迷宮求解.dsw
?????文件???????50176??2011-04-24?14:08??迷宮求解\迷宮求解.ncb
?????文件???????48640??2011-04-24?14:08??迷宮求解\迷宮求解.opt
?????文件?????????752??2011-04-24?14:04??迷宮求解\迷宮求解.plg