迷宫题解--栈

数据结构迷宫问题，2019年蓝桥杯考察题型

#栈的解法
#include<iostream&gt
#define row 10      //行
#define col 10    //列
using namespace std;

int Maze[row][col] = { {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}
};//地图，0是可以走的，1是障碍。

typedef struct
{
    int x; 
    int y;
    int di;
}Box;
typedef struct
{
    Box data[row*col];
    int top;
}StackType;

bool Mazepath(int tx,int ty,int fx,int fy){//求解路径为：(tx,ty)->(fx,fy)
    StackType S;
    int x,y,di,find;

      S.top=-1;   //初始化栈

    S.top++;    //Push操作
    S.data[S.top].x=tx;
    S.data[S.top].y=ty;
    S.data[S.top].di=-1;
    Maze[tx][ty]=-1;  //标记此处已走

    while(S.top>-1){
        //取栈顶方块
        x=S.data[S.top].x;
        y=S.data[S.top].y;
        di=S.data[S.top].di;
        if(x==fx&&y==fy){ //check on if arrived finishing point
            cout<<"顺利抵达"<<  endl;
            for(int k=0;k<=S.top;k++){
                  cout<<"  "<<"("<< S.data[k].x<< ","<< S.data[k].y<< ")";
                if ((k + 1) % 5 == 0)
                    cout<< endl;
            }
            cout<< endl;
            return true;  
        }
        find=0;        //初始化find，find为1则位置可通(只未曾走到过的通道块)

        while(di<4&&find==0){ //四种方向
            di++;
            switch(di){
                case 0: x=S.data[S.top].x-1;
                          y=S.data[S.top].y;
                        break;
                case 1: x=S.data[S.top].x+1;
                          y=S.data[S.top].y;
                        break;
                case 2: x=S.data[S.top].x;
                          y=S.data[S.top].y-1;
                        break;
                case 3: x=S.data[S.top].x;
                          y=S.data[S.top].y+1;
                        break;
            }
            if(Maze[x][y]==0)    find =1;  //位置可通
        }
        if(find==1){    //位置可通
            S.data[S.top].di=di;  //此时di为4
            S.top++;  //选择下个可走的方块进栈（Push操作）
            S.data[S.top].x=x;
            S.data[S.top].y=y;
            S.data[S.top].di=-1;
            Maze[x][y]=-1; //标记去重复
        }
        else //无路可走则退栈
        {
            Maze[S.data[S.top].x][S.data[S.top].y]=0;//复原为可走位置
            S.top--;
        }   
    }
    return false;
}

int main()
{
    if(!Mazepath(1,1,8,8))
        cout<<"无解";
    return 0;
}

SimpleInput：

迷宫图、起点和终点坐标

SimpleOutput：

路径坐标