利用栈求一条迷宫路径（不一定是最优路径）

#include<stdio.h>
#include<malloc.h>
#define MazeRow 10//迷宫的行数
#define MazeCol 10//迷宫的列数

static char Maze[MazeRow][MazeCol] = {  
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},  
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},  
    {'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},  
    {'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},  
    {'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},  
    {'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},  
    {'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},  
    {'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},  
    {'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},  
    {'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}  
};//定义一个迷宫

typedef struct{
    int x;
    int y;
}Pos;//点的坐标
typedef struct data{
    int di;
    Pos seat;
}Data;//每个点的数据
typedef struct Node{
    Data data;
    struct Node * Next;
}SElemType;//栈的节点
typedef struct{
    SElemType * Base;
    SElemType * Top;
}Stack;
Pos Start = {1, 1}, End = {8,8};//入口和出口
Stack s;
void Init_Stack(Stack * s){
    s->Base = (SElemType *)malloc(sizeof(SElemType));
    s->Top = s->Base;
    s->Base->Next = NULL;
}//初始化栈
void Push(Stack * s, data e)
{
    SElemType * p = (SElemType *)malloc(sizeof(SElemType));
    p->data = e;
    p->Next = s->Top;
    s->Top = p;
}//入栈
void Pop(Stack * s, data * e)
{
    SElemType * p = s->Top;
    *e = p->data;
    s->Top = p->Next;
    free(p);
}//出栈
bool Empty(Stack * s)
{
    if(s->Top == s->Base)
        return true;
    else
        return false;
}//判断栈是否为空
Pos NextPos(Pos CurPos, int di)
{
    switch (di)
    {
        case 2:
            (CurPos.x)++;//向南走
            break;
        case 1:
            (CurPos.y)++;//向东走
            break;
        case 4:
            (CurPos.x)--;//向北走
            break;
        case 3:
            (CurPos.y)--;//向西走
    }
    return CurPos;
}//探索下一步
bool Pass(Pos CurPos)
{
    if(Maze[CurPos.x][CurPos.y] == ' ')
        return true;
    else
        return false;
}//判断当前位置是否通
void MarkPrint(Pos Seat)
{
    Maze[Seat.x][Seat.y] = '@';
}//标记出不能走的位置
void FootPrint(Pos CurPos)
{
    Maze[CurPos.x][CurPos.y] = '*';
}//若能走则留下标记
bool Path(Pos Start, Pos End)
{
    data e;
    Init_Stack(&s);
    Pos CurPos = Start;
    int CurStep = 1;
    do{
        if(Pass(CurPos))
        {
            FootPrint(CurPos);
            e.di = 1;
            e.seat = CurPos;
            Push(&s, e);
            if(CurPos.x == End.x && CurPos.y == End.y)
                return true;
        
            CurPos = NextPos(CurPos, 1);
            CurStep++;
        }
        else{
            Pop(&s, &e);
            while(e.di == 4 && !Empty(&s))
            {
                MarkPrint(e.seat);
                Pop(&s, &e);
            }
            if(e.di < 4)
            {
                (e.di)++;
                Push(&s, e);
                CurPos = NextPos(e.seat, e.di);
            }
        }
    }while(!Empty(&s));
    return false;
}//求得路径
void PrintMaze()
{
    int i, j;
    for(i=0; i<MazeRow; i++)
    {
        for(j=0; j<MazeCol; j++)
        {
            printf("%c", Maze[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}//打印迷宫

int main()
{
    PrintMaze();
    if(Path(Start, End))
    {
        PrintMaze();
    }
    else
        PrintMaze();
    return 0;
 }