//應用棧來走迷宮
#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");
    }
}