迷宫求解C++

傷城~ 2022-05-20 00:37 225阅读 0赞

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <algorithm>
    #include <math.h>
    typedef long long ll;
    using namespace std;
    #define Stack_Init_Size 10
    #define STACK_INCREMENT 2
    #define MAX 10
    
    typedef struct{
        int x;
        int y;
    }MazePoint;//迷宫的每个元素
    
    typedef struct{
        MazePoint *top;
        MazePoint *base;
        int StackSize;
    }SqStack;//栈
    
    void InitStack(SqStack &S)
    {
        S.base = (MazePoint *) malloc (Stack_Init_Size * sizeof(MazePoint));
        S.top = S.base;
        S.StackSize = Stack_Init_Size;
    }//初始化栈
    
    bool StackEmpty(SqStack S)
    {
        if(S.top == S.base)
        {
       return true;}
        else  {
       return false;}
    }//判断栈是否为空
    
    void Push(SqStack &S, MazePoint e)
    {
        if((S.top - S.base) >= S.StackSize){
            S.base = (MazePoint *) realloc (S.base, (S.StackSize + STACK_INCREMENT) * sizeof(MazePoint));
            S.top = S.base + S.StackSize;
            S.StackSize =S.StackSize+ STACK_INCREMENT;//空间不足,开辟两个空间
        }
        *S.top = e;
        ++S.top;
    }//入栈
    
    void Pop(SqStack &S, MazePoint &e)
    {
        if(!StackEmpty(S))
            e = *(--S.top);
    }//出栈
    
    void GetTop(SqStack S, MazePoint &e)
    {
        if(S.top > S.base)
            e = *(--S.top);
    }//取栈顶
    void visit(MazePoint e)
    {
        cout<<"("<<e.x<<","<<e.y<<")";
    }//输出迷宫的每个点的坐标
    
    void StackTraverse(SqStack S)
    {
        int i = 0;
        cout<<"**********************"<<endl;
        cout<<"迷宫路径: start";
        while(S.base < S.top){
            cout<<"->";
            visit(*S.base++);
            if((++i)%8 == 0)
                cout<<endl;
        }
        cout<<"->end"<<endl;
    }//出栈时
    
    void InitMaze(int Maze[][MAX], int x,int y)//迷宫输入
    {
        cout<<"请输入Maze:(0为障碍,1为通路) "<<endl;
        for(int i=1;i<=x;i++){
            for(int j=1;j<=y;j++)
            {
                cin>>Maze[i][j];
            }
        }
        for(int i=0;i<=x+1;i++){
            for(int j=0;j<=y+1;j++)
            {
                if((i==0)||(i==x+1)||(j==0)||(j==y+1))
                {
                    Maze[i][j]=0;
                }
            }
        }
    }
    void MazePrint(int Maze[][MAX], int x,int y)//迷宫输出
    {
        for(int i=0;i<=x+1;i++){
            for(int j=0;j<=y+1;j++)
            {
                cout<<Maze[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    void MazePath(int Maze[][MAX], MazePoint start, MazePoint end ,int x,int y)//求迷宫解
    {    //Maze[][MAX]为迷宫, MazePoint start为初始点, MazePoint end 为结束点, int x为长, int y 为宽
        int flag=0,count = 1;
        MazePoint mazeresult;// 通过控制mazeresult对迷宫进行判断上下左右是否有解
        mazeresult = start;
        SqStack s;
        InitStack(s);//初始化栈
        do{    // 通过控制mazeresult对迷宫进行判断上下左右是否有解
            if(Maze[mazeresult.x + 1][mazeresult.y] == 1){
                Push(s,mazeresult);
                //cout<<"hou"<<mazeresult.x<<mazeresult.y<<endl;
                ++mazeresult.x;
                flag = 1;
            }
            else if(Maze[mazeresult.x][mazeresult.y + 1] == 1){
                Push(s,mazeresult);
                //cout<<"you"<<mazeresult.x<<mazeresult.y<<endl;
                ++mazeresult.y;
                flag = 1;
            }
            else if(Maze[mazeresult.x - 1][mazeresult.y] == 1){
                Push(s,mazeresult);
                //cout<<"qian"<<mazeresult.x<<mazeresult.y<<endl;
                --mazeresult.x;
                flag = 1;
            }
            else if(Maze[mazeresult.x][mazeresult.y - 1] == 1){
                Push(s,mazeresult);
                //cout<<"zuo"<<mazeresult.x<<mazeresult.y<<endl;
                --mazeresult.y;
                flag = 1;
            }
            else {flag=0;}
            if(flag==1) Maze[mazeresult.x][mazeresult.y] = ++count;//先加后输出
            else{
                Maze[mazeresult.x][mazeresult.y] = 0;
                Pop(s,mazeresult);
                //cout<<"out"<<mazeresult.x<<mazeresult.y;
                --count;
            }
        }while((mazeresult.x != end.x|| mazeresult.y != end.y ) && !StackEmpty(s));
    
        //cout<<"结束时:"<<mazeresult.x<<mazeresult.y;
        if(mazeresult.x == end.x && mazeresult.y == end.y){
            cout<<"**********************";
            cout<<endl<<"迷宫有解!!"<<endl;
            MazePrint(Maze,x,y);
            StackTraverse(s);
        }
        else{
            cout<<"**********************";
            cout<<endl<<"迷宫无解!!"<<endl;}
    }
    
    int main()
    {
        /* 3 3 1 0 0 0 1 1 0 0 1 无解 3 3 1 1 0 0 1 1 0 0 1 有解 4 4 1 1 1 1 0 0 0 1 0 0 0 1 有解 0 0 0 1 */
        int Maze[MAX][MAX];
        cout<<"Maze的 宽(x) 和 长(y)"<<endl;
        int x,y;
        cin>>x>>y;//Maze的 宽(x) 和 长(y)
        InitMaze(Maze, x, y);//迷宫输入
        cout<<"Print Maze"<<endl;
        MazePrint(Maze ,x ,y );//迷宫输出
        MazePoint start, end;//设置迷宫入口和出口MazePoint
        start.x = start.y = 1;
        end.x = end.y=y;
        MazePath(Maze, start, end, x,y);
        return 0;
    }