栈的应用——迷宫问题

#include<stdio.h>#define MaxSize 100typedef struct{    int i;    int j;    int di;}Box;typedef struct{    Box date[MaxSize];    int top;}StType;bool mgpath(int mg[10][10],int xi,int yi,int xe,int ye);//求解路径为；(xi,yi)->(xe,ye)int main(){    int mg[10][10]=    {        {1,1,1,1,1,1,1,1,1,1},        {1,0,0,1,0,0,0,1,0,1},        {1,0,0,1,0,0,0,1,0,1},        {1,0,0,0,0,1,1,0,0,1},        {1,0,1,1,1,0,0,0,0,1},        {1,0,0,0,1,0,0,0,0,1},        {1,0,1,0,0,0,1,0,0,1},        {1,0,1,1,1,0,1,1,0,1},        {1,1,0,0,0,0,0,0,0,1},        {1,1,1,1,1,1,1,1,1,1}    };    if(!mgpath(mg,1,1,8,8))        PRintf("该迷宫问题没有解！");    return 0;}bool mgpath(int mg[10][10],int xi,int yi,int xe,int ye)//求解路径为；(xi,yi)->(xe,ye){    int i,j,k,di,find;    StType st;//定义栈st    st.top=-1;//初始化栈顶指针    st.top++;//初始化方块进栈    st.date[st.top].i=xi;    st.date[st.top].j=yi;    st.date[st.top].di=-1;    mg[xi][yi]=95;    while(st.top>-1)//栈不空时循环    {        i=st.date[st.top].i;//取栈顶方块        j=st.date[st.top].j;        di=st.date[st.top].di;        if(i==xe&&j==ye)//到了出口输出路径        {            printf("迷宫结果如下（1代表不可走，0代表可走，'_'代表路径）:/n");            for(int n=0;n<10;n++)            {                int m=0;                while(m<10)                {                    if(mg[n][m]==95)                        printf("%2c ",mg[n][m]);                    else                        printf("%2d ",mg[n][m]);                    m++;                }                printf("/n");            }            printf("迷宫路径如下");            printf("/n");            for(k=0;k<= st.top;k++)            {                printf("/t(%d,%d)",st.date[k].i,st.date[k].j);                if((k+1)%5==0)                    printf("/n");            }            printf("/n");            return true;//找到一条路径后返回true        }        find=0;        while(di<4&&find==0)        {            di++;            switch(di)            {            case 0:                i=st.date[st.top].i-1;                j=st.date[st.top].j;                break;            case 1:                i=st.date[st.top].i;                j=st.date[st.top].j+1;                break;            case 2:                i=st.date[st.top].i+1;                j=st.date[st.top].j;                break;            case 3:                i=st.date[st.top].i;                j=st.date[st.top].j-1;                break;            }            if(mg[i][j]==0)//找到下一个可走相邻方块                find=1;        }        if(find==1)//找到下一个可走方块        {            st.date[st.top].di=di;//修改原来栈顶元素di的值            st.top++;       //下一个可走方块进站            st.date[st.top].i=i;            st.date[st.top].j=j;            st.date[st.top].di=-1;            mg[i][j]=95;//避免重复走到该方块        }        else//没有路径可走退栈        {            mg[st.date[st.top].i][st.date[st.top].j]=0;//让该位置变为其他路径可走方块            st.top--;        }    }    return false;//没有路径可走返回法false}
运行结果：