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

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 

相关文章： 宝塔建站无法访问？如何排查配置与端口问题？  企业网站制作公司网页,推荐几家专业的天津网站制作公司？  ,制作一个手机app网站要多少钱？  建站之星在线客服如何快速接入解答？  制作旅游网站html,怎样注册旅游网站？  网站制作怎么样才能赚钱,用自己的电脑做服务器架设网站有什么利弊，能赚钱吗？  建站之星安装失败：服务器环境不兼容？  如何在阿里云购买域名并搭建网站？  如何获取开源自助建站系统免费下载链接？  手机网站制作平台,手机靓号代理商怎么制作属于自己的手机靓号网站？  如何通过FTP服务器快速搭建网站？  个人网站制作流程图片大全,个人网站如何注销？  如何快速启动建站代理加盟业务？  个人摄影网站制作流程,摄影爱好者都去什么网站？  天津个人网站制作公司,天津网约车驾驶员从业资格证官网？  建站之星24小时客服电话如何获取？  娃派WAP自助建站：免费模板+移动优化，快速打造专业网站  linux top下的 minerd 木马清除方法  保定网站制作方案定制,保定招聘的渠道有哪些？找工作的人一般都去哪里看招聘信息？  焦点电影公司作品,电影焦点结局是什么？  南京网站制作费用,南京远驱官方网站？  如何选择最佳自助建站系统？快速指南解析优劣  如何快速搭建高效简练网站？  如何快速使用云服务器搭建个人网站？  厦门模型网站设计制作公司,厦门航空飞机模型掉色怎么办？  如何在IIS服务器上快速部署高效网站？  如何用IIS7快速搭建并优化网站站点？  如何用手机制作网站和网页,手机移动端的网站能制作成中英双语的吗？  零基础网站服务器架设实战：轻量应用与域名解析配置指南  制作网站公司那家好,网络公司是做什么的？  建站之星上传入口如何快速找到？  如何在沈阳梯子盘古建站优化SEO排名与功能模块？  黑客如何通过漏洞一步步攻陷网站服务器？  儿童网站界面设计图片,中国少年儿童教育网站-怎么去注册？  网站海报制作教学视频教程,有什么免费的高清可商用图片网站，用于海报设计？  建站之星代理如何获取技术支持？  太平洋网站制作公司,网络用语太平洋是什么意思？  建站主机选购指南：核心配置与性价比推荐解析  官网建站费用明细查询_企业建站套餐价格及收费标准指南  网站制作培训多少钱一个月,网站优化seo培训课程有哪些？  建站主机与服务器功能差异如何区分？  建站之星免费模板：自助建站系统与智能响应式一键生成    孙琪峥织梦建站教程如何优化数据库安全？  高配服务器限时抢购：企业级配置与回收服务一站式优惠方案  如何选择香港主机高效搭建外贸独立站？  全景视频制作网站有哪些,全景图怎么做成网页？  广德云建站网站建设方案与建站流程优化指南  北京网站制作的公司有哪些,北京白云观官方网站？  网站制作大概多少钱一个,做一个平台网站大概多少钱？