//應用棧來走迷宮
#include<stdio.h>
#include<stdlib.h>
struct stack_node
{
int x;//路徑坐標x
int y;//路徑坐標y
struct stack_node *next;//指向下一結點
};
typedef struct stack_node stack_list;
typedef stack_list *link;
link path=NULL;//路徑棧指針
//棧數據的存入
link push(link stack,int x,int y)
{
link new_node;//新結點指針
//分配結點內存
new_node=(link)malloc(sizeof(stack_list));
if(!new_node)
{
printf("內存分配失敗!\n");
return NULL;
}
new_node->x=x; //存入路徑坐標x
new_node->y=y; //存入路徑坐標y
new_node->next=stack;//新結點指向原開始
stack=new_node; //新結點成為棧開始
return stack;
}
//棧數據的取出
link pop(link stack,int *x,int *y)
{
link top;//指向棧頂端
if(stack!=NULL)
{
top=stack;
stack=stack->next;//棧指針指向下結點
*x=stack->x;//取出路徑坐標x
*y=stack->y;//取出路徑坐標y
free(top);
return stack;
}
else
*x=-1;
}
//主程序：用回溯的方法在數組迷宮找出口
//數字0:表示是可以走的路
//數字1:表示是墻壁，不可走的路
//數字2:表示是走過的路
//數字3:表示是回溯的路
void main()
{
int maze[7][10]={
1,1,1,1,1,1,1,1,1,1,
1,0,1,0,1,0,0,0,0,1,
1,0,1,0,1,0,1,1,0,1,
1,0,1,0,1,1,1,0,0,1,
1,0,1,0,0,0,0,0,1,1,
1,0,0,0,1,1,1,0,0,1,
1,1,1,1,1,1,1,1,1,1,};
int i,j;
int x=5;//迷宮入口坐標
int y=8;
while(x!=1||y!=1)//是否是迷宮出口
{
maze[x][y]=2;//標示走過的路
if(maze[x-1][y]<=0) //往上方走
{
x=x-1;
path=push(path,x,y);//存入路徑
}
else if(maze[x+1][y]<=0)//往下方走
{
x=x+1;
path=push(path,x,y);
}
else if(maze[x][y-1]<=0)//往左方走
{
y=y-1;
path=push(path,x,y);
}
else if(maze[x][y+1]<=0)//往右方走
{
y=y+1;
path=push(path,x,y);
}
else
{
maze[x][y]=3;
path=pop(path,&x,&y);//退回一步
}
}
maze[x][y]=2;
printf("迷宮的路徑如下圖所示:\n");
for(i=1;i<6;i++)//輸出迷宮圖形
{
for(j=1;j<9;j++)
printf("%d",maze[i][j]);//輸出各坐標
printf("\n");
}
}