数据结构——迷宫问题(顺序栈、C++)

这篇具有很好参考价值的文章主要介绍了数据结构——迷宫问题(顺序栈、C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 讲解:

一、采用二维数组和srand函数随机生成只有0和1的迷宫。

二、求解迷宫大概思路:先将入口处的坐标即方向d入栈,然后当栈不为空时,取出栈顶(即当前节点)的数据。遍历当前节点的四个方向,找到可行的下一个节点,并将其入栈;如没有可行的下一个节点,则将当前节点值0(表示未走过),然后出栈,退回到前一个节点进行遍历。当栈顶数据和出口一致时,输出迷宫的通路。

#include <iostream>
#include <time.h>
#define M 100
#define N 100
#define MAXSIZE 100
using namespace std;

int maze[M][N];

void CreateMaze(int m, int n)       //创建迷宫
{
    srand(time(NULL));
    for(int i=1;i<m+1;i++)
    {
        for(int j=1;j<n+1;j++)
        {
           maze[i][j] = rand()%2;    //只有0和1的随机迷宫
        }
    }

    maze[1][1] = -1; //直接入口置-1,表示可走
    maze[m][n] = 0; //出口

    for(int i=0;i<m+2;i++) maze[i][0] = 1;    //设置围墙
    for(int i=0;i<m+2;i++) maze[i][m+1] = 1;
    for(int j=0;j<n+2;j++) maze[0][j] = 1;
    for(int j=0;j<n+2;j++) maze[n+1][j] = 1;
}

void Print(int m,int n)              //打印迷宫
{
    for(int i=0;i<m+2;i++)
    {
        for(int j=0;j<n+2;j++)
        {
            if(maze[i][j] == 0)
              cout << "  ";
            if(maze[i][j] == 1)
              cout << "□";
        }
        cout << endl;
    }

}

typedef struct    //定义当前位置坐标
{
    int x;
    int y;
    int d;   //移动方向
}Point;

typedef struct    //定义顺序栈
{
    Point data[MAXSIZE];  //定义顺序栈的存储类型为结构体data
    int top;
}SqStack;

bool MazePath(int x1,int y1,int m, int n)
{
    int i,j,d,find;
    SqStack S;
    S.top = -1;  //初始化栈
    S.top++;
    S.data[S.top].x = x1; S.data[S.top].y = y1; S.data[S.top].d = -1;
    while(S.top>-1)
    {
        i = S.data[S.top].x; j = S.data[S.top].y; d = S.data[S.top].d;
        if(i==m&&j==n)
        {
            cout << "找到路径:" << endl;
            for(int i=0;i<m+2;i++)
            {
                for(int j=0;j<n+2;j++)
                {
                    if(maze[i][j] == 1)
                        cout << "□";
                    else if(maze[i][j] == 0)
                        cout << "  ";
                    else
                        cout << " *";
                }
                cout << endl;
            }
        return true;
        }


        find = 0;        //设置标识,1表示找到下一个可行路径,0表示没有找到
        while(d<4&&find==0)       //遍历4个方向:0->东,1->南,2->西,3->北
        {
            d++;
            switch(d)
            {
            case 0:
                i = S.data[S.top].x+1; j = S.data[S.top].y; break;
            case 1:
                i = S.data[S.top].x; j = S.data[S.top].y+1; break;
            case 2:
                i = S.data[S.top].x-1; j = S.data[S.top].y; break;
            case 3:
                i = S.data[S.top].x; j = S.data[S.top].y-1; break;
            }
            if(maze[i][j] == 0) find = 1;  //找到路径,标识置1,退出循环
        }

        if(find == 1)  //找到路径
        {
            S.data[S.top].d = d;  //记录当前节点往下一个节点的方向
            S.top++;              //下一个节点入栈
            S.data[S.top].x = i;
            S.data[S.top].y = j;
            S.data[S.top].d = -1;  //将下一个节点的走向置为-1
            maze[i][j] = -1;  //当前点置-1,表示走过
        }
        else  //未找到路径
        {
            maze[S.data[S.top].x][S.data[S.top].y] = 0;  //当前点置为0,表示未走过
            S.top--;  //出栈
        }
    }
    return false;
}


int main()
{
    int m,n;
    int k=1;
    while(k)
    {
      cin >> m >> n;
      CreateMaze(m,n);
      Print(m,n);
      if(!MazePath(1,1,m,n))
      {
            cout << "找不到路径"<<endl;
            k++;
      }
    else k=0;
    }
}

运行结果:(由于随机生成大概率没有通路,所以输出较小的迷宫容易出结果)

迷宫问题数据结构,c++,数据结构

迷宫问题数据结构,c++,数据结构

 

 写的很简陋,有不足之处请指正。文章来源地址https://www.toymoban.com/news/detail-541832.html

到了这里,关于数据结构——迷宫问题(顺序栈、C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构与算法分析》课程设计——迷宫问题

    中国矿业大学信控学院   补一下我之前在博客园发布的内容  懒得调了, 想复制完整代码直接复制最下面的 ,想复制分布代码去看我博客园链接吧 《数据结构与算法分析》课程设计——迷宫问题 - 刷子zz - 博客园 一、  问题描述 问题中迷宫可用方阵[m,n]表示,0表示能通过

    2024年02月10日
    浏览(49)
  • 【数据结构】迷宫问题DFS非递归(c语言实现)

    本来之前写过一个推箱子,就想着写个迷宫游戏,因为想着推箱子游戏里面也有墙,也有玩家的移动,比推箱子简单的是还不用判断前面是否有箱子的情况,但是自己写的迷宫游戏如果自己随机生成的迷宫地图的话,不一定会有通路,他要学一个什么随机迷宫的生成,刚看完

    2024年02月08日
    浏览(37)
  • 数据结构与算法—顺序表、链接表、顺序栈、链接栈、顺序队列、链接队列的C++代码实现

    线性表是一种常见的数据结构,具有以下几个特点: 元素的有限序列:线性表是由有限个元素组成的有序序列,每个元素的位置都是唯一确定的。 线性结构:线性表中的元素只有一个前驱和一个后继,除第一个和最后一个元素外,每个元素都有一个前驱和一个后继。 线性表

    2024年02月08日
    浏览(39)
  • 【数据结构篇C++实现】- 线性表 - 顺序表和链表

    友情链接:C/C++系列系统学习目录 故事导入: 幼儿园放学时,一个班级的小朋友,一个跟着一个排队出校,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面和后面的一个是谁,就如同一根线把他们串联了起来。如此具有像线一样的性质的表就叫线性表 线性表(

    2024年02月07日
    浏览(54)
  • 数据结构与算法—一维数组、二维数组、矩阵、顺序串、链接串的C++代码实现

    1、一维数组:ArrayOneD.h 数组这种数据结构可以看作线性表的推广。数组一般采用顺序存储的方法表示。 这是一个模板类 ArrayOneD 的实现,用于表示一维数组。它包括了 构造函数、拷贝构造函数、析构函数、重载下标运算符、重载赋值运算符、求数组长度、重新设置数组长度

    2024年02月07日
    浏览(60)
  • 数据结构-线性表的顺序表基本操作代码实现(超级详细清晰 C++实现)

    顺序表是用一段 物理地址连续的存储单元 依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表: 可动态增长的数组,要求数据是连续存储的 特点: 随机访问 顺序既可以 静态分配 ,也可以 动态分配 。在静态分配时,由于数组

    2024年02月07日
    浏览(54)
  • C++数据结构之查找——静态查找表(顺序查找、折半查找、分块查找 带有gif以及图示)

    目录 一、查找的相关概念介绍 1.查找表(Search Table) 概念 对查找表的操作 查找表的分类 2.(Key) 概念 3.查找(Searching) 概念 4.衡量查找算法的标准 1.时间复杂度 2.空间复杂度 3.平均查找长度(ASL) 二、静态查找表 1.顺序查找 算法思路 算法举例 算法性能分析 不等概率

    2024年02月03日
    浏览(44)
  • 数据结构中: 一元多项式的运算(相加,相减,相乘)------用C语言 / C++来实现。 数据结构线性表的操作和应用(顺序存储)

    线性表的操作和应用(顺序存储)。用顺序存储实现一元多项式,并进行加、减、乘运算。 (1)一元多项式结构体创建  (2)初始化 (3)一元多项式赋值             (4)打印一元多项式 (5)加法运算                        (6)减法运算 (7)乘法运算    全部代

    2024年02月01日
    浏览(57)
  • 【数据结构之二叉树简介·顺序存储·应用:堆·堆排序·TOPK问题】

    ​ 🕺作者: 迷茫的启明星 😘欢迎关注:👍点赞🙌收藏✍️留言 🎃相关文章 【数据结构从0到1之树的初识】 【数据结构】带你学会二叉树的链式存储的前中后序遍历,遍历推导及利用队列实现二叉树的层次遍历。 🏇家人们,码字不易,你的👍点赞🙌收藏❤️关注对我

    2024年02月01日
    浏览(35)
  • 数据结构--迷宫求解

    文章目录 一、问题的描述 二、系统功能设计 三、各个代码部分 四、整体代码及其运行 五、总结 迷宫求解--C语言 在一个迷宫中,需要我们找到出去的道路,并且得到的路经是最短的。 迷宫设置如下:迷宫使用标记(0,1,2,3分别代表迷宫的墙壁,通道,入口和出口) 从开

    2024年02月15日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包