基于c++深度优先遍历迷宫

简介: 基于c++深度优先遍历迷宫

c++实现的深度优先遍历迷宫,迷宫大小为20*20,代码简练清楚,内涵关键注释。代码与网上都不一样。

深度优先遍历迷宫,核心思想是借助一个栈,站在一个节点上时,将它附近可以走的节点存在栈中,再按顺序找到下一个节点,重复刚才的操作,直到找到最终的终点。


实现细节


  • Stack函数不需要多说了,自己定义一个栈,这个栈是很关键的,像我刚才说的,他用来记录去过的节点,以保证不重不漏
  • 重点是slove函数,slove()原理: 递归出口为找到出口或者没有出口的条件下整个地图被全部遍历将入口读出;分别进行上下左右移动并判定是否可走;如果可走则将其压栈,并递归;否则返回上一步。这是一个递归函数,因此深度优先本身的效率不高。 对于一个节点,坐标(x,y),我们这里规定只允许向四个方向移动,所以需要找的坐标是(x-1,y),(x+1,y)(x,y-1),(x,y+1),分别判断是否可以去,且是否去过,这就是本项目中最重要的地方了!
void slove(zuobiao c,Stack &a,int (*Map)[20]){
  zuobiao l=a.ntop();
  if(l.x==c.x&&l.y==c.y){
    return ;
  }
  if(pass(l.x,l.y+1,Map)){
    zuobiao m;
    m.x=l.x;m.y=l.y+1;
    vi[m.x][m.y]=1;
    a.push(m);  
    slove(c,a,Map);
  }
  else if(pass(l.x,l.y-1,Map)){
    zuobiao m;
    m.x=l.x;m.y=l.y-1;
    vi[m.x][m.y]=1;
    a.push(m);  
    slove(c,a,Map);
  }
  else if(pass(l.x-1,l.y,Map)){ 
    zuobiao m;
    m.x=l.x-1;m.y=l.y;
    vi[m.x][m.y]=1;
    a.push(m);  
    slove(c,a,Map);
  }
  else if(pass(l.x+1,l.y,Map)){
    zuobiao m;
    m.x=l.x+1;m.y=l.y;
    vi[m.x][m.y]=1;
    a.push(m);  
    slove(c,a,Map);
  }
  else {
      if(a.bout()){
      slove(c,a,Map);
      }
      else {
      cout<<"没有路径可以到达指定的地点";
      }
  }
}




2746c9f87255120f05a7f510bd223a5c.png


目录
打赏
0
0
0
0
29
分享
相关文章
【C++之迭代器】遍历容器
【C++之迭代器】遍历容器
【C++之数组与指针1】随机输入整数存入数组并用指针遍历
【C++之数组与指针1】随机输入整数存入数组并用指针遍历
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
48 2
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
42 0
【C++篇】深入内存迷宫:C/C++ 高效内存管理全揭秘
【C++篇】深入内存迷宫:C/C++ 高效内存管理全揭秘
149 3
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之vector容器操作(构造、赋值、扩容、插入、删除、交换、预留空间、遍历)
C++之vector容器操作(构造、赋值、扩容、插入、删除、交换、预留空间、遍历)
378 0
|
8月前
|
C++
C++数组(定义、遍历、长度、地址、最大值、逆置、冒泡排序)
C++数组(定义、遍历、长度、地址、最大值、逆置、冒泡排序)
123 0
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
【见微知著】OpenCV中C++11 lambda方式急速像素遍历
80 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等