#include?
#include?
#include
#include
#define?M?120
#define?N?120
#define?MAXLEN?M*N
int?sxsyexey;
int?nm;
char?maze[M][N];
double?BeginTimeconsumeFinish;//時間消耗
?
?

typedef?struct//棧元素類型
{???int?xydir;
}elemtype;

typedef?struct//棧結構
{??elemtype?stack[MAXLEN];
???int?top;
}?sqstack;

?typedef?struct//隊列元素類型
{???int?xypre;
????
}QueueNode;

typedef?struct//隊列結構
{???QueueNode?queue[MAXLEN];
????int?front?rear;
}SqQueue;?

struct?moved//方向數組結構體類型
{???int?dxdy;
};


void?inimove（struct?moved?move[]）//初始化方向數組
{????move[0].dx=0;move[0].dy=1;
?????move[1].dx=1;move[1].dy=0;
?????move[2].dx=0;move[2].dy=-1;
	?move[3].dx=-1;move[3].dy=0;
}


void?inistack（sqstack?*s）//初始化棧
{????s->top=-1;

}

int?push（sqstack?*selemtype?x）//入棧操作
{???if（s->top==MAXLEN-1）
????????return?0;
????else
	{????s->stack[++s->top]=x;
	?????return?1;
	}
}

elemtype?pop（sqstack?*s）//出棧操作
{elemtype?elem;
????if（s->top<0）
	{???elem.x=NULL;
????????elem.y=NULL;
	????elem.dir=NULL;
	????return?elem;
	}
????else?
	{???s->top--;
????????return（s->stack[s->top+1]）;
	}
}


void?iniqueue（SqQueue?*s）
{????s->front=1;
?????s->rear=1;
}


int?shortpath（char?maze[][N]struct?moved?move[]SqQueue?*p）//尋找最段路徑?
{????int?ijxydir;
?????p->queue[1].x=sx;
?????p->queue[1].y=sy;
	?p->queue[1].pre=0;
	?maze[sx][sy]=-1;
	?while（p->front<=p->rear）
	?{????i=p->queue[p->front].x;//ij為出發點
	??????j=p->queue[p->front].y;?
	??????for（dir=0;dir<4;dir++）//尋找從ij出發四個方向有那些可以到達
		??{????x=i+move[dir].dx;
		???????y=j+move[dir].dy;
		???????if（maze[x][y]==‘O‘）//?如有可到達點將此點入隊
			???{???p->rear++;
			???????p->queue[p->rear].x=x;
				???p->queue[p->rear].y=y;
				???p->queue[p->rear].pre=p->front;
				???maze[x][y]=-1;
			???}
			???if（（x==ex）&&（y==ey））//如到達出口返回真
			??????return?1;
		??}
	??????p->front++;//對頭指針指向下一隊列元素
	}
	return?0;
}


void?printpath（SqQueue?*psqstack?*s）//將最短路徑入棧
{????int?if;
?????elemtype?elem;
	?i=p->front;
	?do//從隊列中取出最短迷宮路經放入棧中
	?{???elem.x=p->queue[i].x;
?????????elem.y=p->queue[i].y;
		?f=push（selem）;
		??if（f==0）
		?????printf（“棧長度太短\n“）;
		??i=p->queue[i].pre;
		???	?
	}while（i>0）;//不變了
	printf（“\n“）;
}


void?draw（char?maze[][N]sqstack?*s）//將路徑從棧中彈出還原為原來的并以P代O
{????int?ij;
?????elemtype?elem;
	?for（i=1;i<=M;i++）
	??????for（j=1;j<=N;j++）
		???if（maze[i][j]==-1）
				?maze[i][j]=‘O‘;
	?while（s->top>-1）
	?{???elem=pop（s）;
	?????i=elem.x;
		?j=elem.y;
		?maze[i][j]=‘P‘;
	??}?
	maze[sx][sy]=‘S‘;
	for（i=1;i<=m;i++）//輸出找到路徑后的迷宮
	{for（j=1;j<=n;j++）
		{printf（“%c“maze[i][j]）;
????????}
	????printf（“\n“）;
	}
}
	

int?main（）
{
	FILE?*fp;
	char?filename[10];
	int?ijf;
????sqstack?*s;
	SqQueue?*p;
????printf（“Please?input?the?file?name:“）;
	scanf（“%s“filename）;
	
	fp=fopen（filename“r“）;
	if（fp==NULL）
???	{	printf（“打開失敗“）;
	????exit（1）;
	}
	fscanf（fp“%d“&m）;
	fscanf（fp“%d“

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

?????文件???????2608??2007-11-29?16:03??maze.txt

?????文件???????4293??2007-12-05?09:24??maze.cpp

?????文件?????217146??2007-11-29?16:05??maze.exe

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

???????????????224047????????????????????3