数据结构课程设计- (二) 栈与队列(迷宫问题)

末蓝、 2022-12-28 01:35 149阅读 0赞

迷宫问题求解  
任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；  
要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

利用栈实现各个方向的存储，若走到死路则退到前一格，实现寻找路径的功能：

#include <bits/stdc++.h>
    using namespace std;
    #define maxsize 100
    typedef struct point//点
    {
        
        int x,y,dir;//1234上下左右
    }block;
    typedef struct Stack//栈
    {
        
        block b[maxsize];
        int top;
    }Linkstack;
    int isempty(Linkstack S)//判空
    {
        
        if(S.top==-1)
        {
        
            return 1;
        }
        else
        {
        
            return 0;
        }
    }
    void inStack(Linkstack &s,block point)//进栈
    {
        
        s.top++;
        s.b[s.top]=point;
    }
    block outStack(Linkstack &s)//出栈
    {
        
        block a=s.b[s.top];
        s.top--;
        return a;
    }
    void Initstack(Linkstack &s)//初始化
    {
        
        s.top=-1;
    }
    int solve()
    {
        
        int i,j,dir,found=0;
        int m,n;
        printf("输入迷宫行数和列数\n");
        scanf("%d%d",&m,&n);
        int a[m][n];
        printf("输入迷宫结构,1为墙,0可走\n");
        for(i=0;i<m;i++)
        {
        
            for(j=0;j<n;j++)
            {
        
                scanf("%d",&a[i][j]);
            }
        }
        int x1,y1,x2,y2;
        printf("输入起点和终点\n");
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int jixu=1;
        if(a[x1][y1]=='1')
        {
        
            printf("入口选择错误");
            jixu=0;
        }
        if(a[x2][y2]=='1')
        {
        
            printf("出口选择错误");
            jixu=0;
        }
        Linkstack s;
        Initstack(s);
        s.top++;
        s.b[s.top].x=x1,s.b[s.top].y=y1;
        s.b[s.top].dir=0;
        a[x1][y1]=-1;//防重复
        if(jixu==1){
        
        while(isempty(s)!=1)
        {
        
            i=s.b[s.top].x,j=s.b[s.top].y;
            dir=s.b[s.top].dir;
            if(i==x2&&j==y2)//找到终点
            {
        
                printf("路径如下：\n");
                for(int k=0;k<=s.top;k++)//输出栈中内容
                {
        
                        printf("(%d,%d)",s.b[k].x,s.b[k].y);
                        int to=s.b[k].dir;
                        if(to==1)
                        {
        
                         printf("再向上一格\n");
                        }
                        else if(to==2)
                        {
        
                            printf("再向下一格\n");
                        }
                        else if(to==3)
                        {
        
                            printf("再向左一格\n");
                        }
                        else if(to==4)
                        {
        
                            printf("再向向右一格\n");
                        }
                }
                return 1;
            }
            found=0;
            dir=0;
            while(dir<=4&&found==0)
            {
        
                dir++;
                //printf("%d",dir);
                switch(dir)
                {
        
                    case 1:i=(s.b[s.top].x-1);j=s.b[s.top].y;break;
                    case 2:i=(s.b[s.top].x+1);j=s.b[s.top].y;break;
                    case 3:i=s.b[s.top].x;j=(s.b[s.top].y-1);break;
                    case 4:i=s.b[s.top].x;j=(s.b[s.top].y+1);break;
                }
                if(a[i][j]==0)//要走的方向不是墙体
                {
        
                 found=1;
                }
            }
            if(found==1)//找到一个可以走的
            {
        
                s.b[s.top].dir=dir;
                block q;
                q.x=i,q.y=j;
                q.dir=dir;
                inStack(s,q);//入栈
                a[i][j]=-1;
                dir=0;
            }
            else//找不到了，该点是死路，退栈
            {
        
                a[s.b[s.top].x][s.b[s.top].y]=0;
                s.top--;
            }
        }}
        return 0;
    }
    int main()
    {
        
        int a=solve();
        if(a==0)printf("未找到路线\n");
    }

输入:  
1 1 1 1 1 1  
1 0 0 1 1 1  
1 1 0 1 1 1  
1 1 0 0 0 1  
1 1 1 1 0 1  
1 1 1 1 1 1

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]: /images/20221120/15fe05e9bba64a03a0360fc44fa19684.png