C++ 自定义栈实现迷宫求解

一：迷宫求解

是一个锻炼我们的算法求解能力的问题，它的实现方法有很多；今天我们就介绍其中的用栈求解的方法。

二：什么是栈：

      大家应该都有往袋子里装东西的经历，在往袋子里装满东西之后，当我们去取的时候，总是先从最后放进去的东西的地方去取。也就是后进先出(FILO)。虽然栈的单向性用起来会没有链表那样可以在任意位置对数据进行操作，但是正因为如此栈也带来了很大的方便。

三：迷宫求解

现在我们要在下面的迷宫寻找一条可行的路径

 1 1 1 1 1 1 1 1 1 1
 1 0 0 1 1 0 0 0 0 1
 1 0 0 0 1 0 1 0 0 1
 1 0 1 0 0 0 1 1 0 1
 1 0 1 0 0 0 1 1 1 1
 1 0 1 1 1 0 1 1 1 1
 1 0 1 1 1 0 1 1 1 1
 1 1 1 1 1 0 0 0 1 1
 1 1 1 1 1 1 1 0 0 1
 1 1 1 1 1 1 1 1 1 1

首先我们需要在程序中表示上面的迷宫，该问题可以用数组实现

1：栈的定义

/************************************************************************/ 
/*自定义栈                                     */ 
/*通过自定义的简单栈以满足迷宫求解        */ 
/*功能：push() 将元素加入栈中                 */ 
/*        pop() 退栈；topValue() 获得栈顶元素    */ 
/*        clear() 清除栈 length() 获得栈中元素个数*/ 
/************************************************************************/ 
#include <stack> 
#include <iostream> 
using namespace std; 
 
template<typename Elem> class PathStack: public stack<Elem> 
{ 
private: 
  int size; 
  int top; 
  Elem* listArray; 
public: 
  PathStack(int sz = DefaultListSize){ 
    size = sz; 
    top = 0; 
    listArray = new Elem[sz]; 
  } 
  ~PathStack(){ delete []listArray; } 
  void clear(){ top = 0; } 
  /****向栈中加入元素****/ 
  bool push(const Elem& item); 
  /***********退栈**********/ 
  Elem pop(); 
  /********获得栈顶元素*******/ 
  Elem topValue() const; 
  int length() const { return top; } 
}; 
 
template<typename Elem> 
bool PathStack<typename Elem>::push(const Elem& item){ 
  if(top == size) return false; 
  listArray[top++] = item; 
  return true; 
} 
 
template<typename Elem> 
Elem PathStack<typename Elem>::pop(){ 
  Elem it; 
  if(top == 0) return it; 
  it = listArray[--top];  
  return it; 
} 
 
template<typename Elem> 
Elem PathStack<typename Elem>::topValue() const{ 
  Elem it; 
  if(top == 0) return it; 
  it = listArray[top - 1]; 
  return it; 
} 

  2：如何实现路径的寻找

     1：设定寻找的方向，可以使用一个判断语句；判断起始位置周围哪个地方有路就将该位置的坐标加入到栈中，并将该位置标记(将改位置值改为2,既将走过的位置标记为2)

     2：判断该位置周围是否还有路，若没有则退栈即退回到上一个位置；并将该位置做下另一个标记(将该位置值改为3,既将退栈位置值用3标记)

     3：重复1,2步骤直到达到出口

     路径寻找的类： 

//迷宫求解的方法类 
//功能：通过findPath() 方法实现对路径的查找 
//       通过printPath()方法将路径打印出来 
#include "PathStack.h" 
#include <iostream> 
using namespace std; 
 
class MazeSolveMethod 
{ 
private: 
  static int maze[10][10];//存放迷宫数据 
  PathStack<int> pathStack;//定义栈 
public: 
  MazeSolveMethod():pathStack(100){ 
  } 
  ~MazeSolveMethod(){ } 
  void findPath(int startX,int startY); 
  void printPath() const; 
}; 
 
int MazeSolveMethod::maze[10][10] = { 
  {1,1,1,1,1,1,1,1,1,1}, 
  {1,0,0,1,1,0,0,0,0,1}, 
  {1,0,0,0,1,0,1,0,0,1}, 
  {1,0,1,0,0,0,1,1,0,1}, 
  {1,0,1,0,0,0,1,1,1,1}, 
  {1,0,1,1,1,0,1,1,1,1}, 
  {1,0,1,1,1,0,1,1,1,1}, 
  {1,1,1,1,1,0,0,0,1,1}, 
  {1,1,1,1,1,1,1,0,0,1}, 
  {1,1,1,1,1,1,1,1,1,1}, 
}; 
 
void MazeSolveMethod::findPath(int startX,int startY){ 
  int x = startX; 
  int y = startY; 
  pathStack.push(x); 
  pathStack.push(y); 
  maze[x][y] = 2; 
  cout<<"进入方法！"<<endl; 
  while(true){ 
    if(maze[x-1][y] == 0){ 
      pathStack.push(--x); 
      pathStack.push(y); 
      maze[x][y] = 2; 
    }else if(maze[x][y-1] == 0){ 
      pathStack.push(x); 
      pathStack.push(--y); 
      maze[x][y] = 2; 
    }else if(maze[x][y+1] == 0){ 
      pathStack.push(x); 
      pathStack.push(++y); 
      maze[x][y] = 2; 
    }else if(maze[x+1][y] == 0){ 
      pathStack.push(++x); 
      pathStack.push(y); 
      maze[x][y] = 2; 
    } 
    if(maze[x-1][y] != 0 && maze[x][y+1] != 0 && maze[x+1][y] != 0 && maze[x][y-1] != 0){         
      if(x >= 8 && y >= 8){ 
        break; 
      }else{ 
        maze[x][y] = 3; 
        y = pathStack.pop(); 
        x = pathStack.pop(); 
      } 
      y = pathStack.topValue(); 
      int temp = pathStack.pop(); 
      x = pathStack.topValue(); 
      pathStack.push(temp); 
    } 
  } 
} 
 
void MazeSolveMethod::printPath() const{ 
  cout<<"printPath"<<endl; 
  for(int i=0; i<10; i++){ 
    for(int j=0; j<10; j++){ 
      if(maze[i][j] == 2) 
        cout<<'*'<<" "; 
      else if(maze[i][j] == 3) 
        cout<<0<<" "; 
      else 
        cout<<1<<" "; 
    } 
    cout<<endl; 
  } 
} 

   主函数类 

/************************************************************************/ 
/*迷宫求解----栈方法实现*/ 
//功能：通过对栈实现迷宫算法求解 
//Author：Andrew 
//Date  ：2012-10-20 
/************************************************************************/ 
#include "MazeSolveMethod.h" 
#include <iostream> 
using std::cout; 
using std::endl; 
 
int main(){ 
 
  MazeSolveMethod solve; 
  solve.findPath(1,1); 
  solve.printPath(); 
  system("pause"); 
  return 0; 
} 

 将上面的代码运行后结果截图如下：

 其中* 为路径 

 感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# C++  # 自定义栈实现迷宫  # 迷宫求解  # C++通过自定义函数找出一个整数数组中第二大数的方法  # C++自定义数据类型方法详情  # C语言编程C++自定义个性化类型  # 解决易语言转换到C++ 自定义数据类型  # C++自定义函数判断某年某月某日是这一年中第几天  # c++模板自定义数组  # 将该  # 自定义  # 是一个  # 都有  # 有很多  # 可以用  # 要在  # 希望能  # 带来了  # 可以使用  # 当我们  # 谢谢大家  # 如何实现  # 里装  # 打印出来  # 袋子里  # 链表  # 以满足  # namespace  # std 

相关栏目： 【 网站优化151355 】 【 网络推广146373 】 【 网络技术251813 】 【 AI营销90571 】

相关推荐： 胶州企业网站制作公司,青岛石头网络科技有限公司怎么样？  HTML透明颜色代码在Angular里怎么设置_Angular透明颜色使用指南【详解】  如何快速搭建安全的FTP站点？  如何自己制作一个网站链接,如何制作一个企业网站，建设网站的基本步骤有哪些？  php静态变量怎么调试_php静态变量作用域调试技巧【解答】  Swift开发中switch语句值绑定模式  Android 常见的图片加载框架详细介绍  Laravel中的Facade(门面)到底是什么原理  如何利用DOS批处理实现定时关机操作详解  iOS UIView常见属性方法小结  java中使用zxing批量生成二维码立牌  标题：Vue + Vuex 项目中正确使用 JWT 进行身份认证的实践指南  Laravel如何实现模型的全局作用域？（Global Scope示例）  网易LOFTER官网链接 老福特网页版登录地址  桂林网站制作公司有哪些,桂林马拉松怎么报名？  如何在腾讯云服务器上快速搭建个人网站？  详解Nginx + Tomcat 反向代理 负载均衡 集群 部署指南  微信推文制作网站有哪些,怎么做微信推文，急？  常州企业网站制作公司,全国继续教育网怎么登录？  深圳网站制作的公司有哪些,dido官方网站？  JavaScript数据类型有哪些_如何准确判断一个变量的类型  Laravel如何构建RESTful API_Laravel标准化API接口开发指南  哪家制作企业网站好,开办像阿里巴巴那样的网络公司和网站要怎么做？  专业商城网站制作公司有哪些,pi商城官网是哪个？  实例解析angularjs的filter过滤器  如何快速辨别茅台真假？关键步骤解析  Laravel如何处理表单验证？（Requests代码示例）  Laravel怎么配置S3云存储驱动_Laravel集成阿里云OSS或AWS S3存储桶【教程】  网站设计制作书签怎么做,怎样将网页添加到书签/主页书签/桌面？  油猴 教程,油猴搜脚本为什么会网页无法显示？  移动端手机网站制作软件,掌上时代，移动端网站的谷歌SEO该如何做？  googleplay官方入口在哪里_Google Play官方商店快速入口指南  EditPlus中的正则表达式实战(5)  如何制作公司的网站链接,公司想做一个网站，一般需要花多少钱？  详解Oracle修改字段类型方法总结  如何在宝塔面板中创建新站点？  晋江文学城电脑版官网 晋江文学城网页版直接进入  Laravel怎么清理缓存_Laravel optimize clear命令详解  php打包exe后无法访问网络共享_共享权限设置方法【教程】  Laravel Seeder填充数据教程_Laravel模型工厂Factory使用  大连网站制作费用,大连新青年网站，五年四班里的视频怎样下载啊？  如何在Windows虚拟主机上快速搭建网站？  如何续费美橙建站之星域名及服务？  潮流网站制作头像软件下载,适合母子的网名有哪些？  Laravel观察者模式如何使用_Laravel Model Observer配置  极客网站有哪些,DoNews、36氪、爱范儿、虎嗅、雷锋网、极客公园这些互联网媒体网站有什么差异？  ai格式如何转html_将AI设计稿转换为HTML页面流程【页面】  如何获取上海专业网站定制建站电话？  Laravel如何实现API速率限制？（Rate Limiting教程）  北京网站制作费用多少,建立一个公司网站的费用.有哪些部分,分别要多少钱？