C++实现迷宫生成与解决
更新时间:2020年12月21日 20:10 点击:1699
数据结构实验课要求解决一个迷宫问题,这里给定长宽用prime算法随机生成了一个迷宫并从指定起点与终点打印出了迷宫的解决方案,此处用到了栈数据结构,这里的jmc::Stack是我自己写的栈,这里就不放了,可以换成一切具有常规意义的empty、pop、push接口的栈ADT,或者直接使用std::stack就行,注意头文件的#include"Stack"也改一下
Maze.h:
#pragma once #include<iostream> #include<vector> #include<map> #include<set> #include<random> #include<string> #include"Stack.h" #include<functional> #include<algorithm> #include<cassert> namespace jmc { using blockpic = std::vector<std::string>; const blockpic block{ "▉"," ","※" }; class locat { public: using rowType = size_t; using calType = size_t; locat(rowType r = 0, calType c = 0) :loc(r, c) {} rowType x(void)const { return loc.first; } //返回一维坐标 rowType x(const rowType& r) { loc.first = r; return loc.first; }//修改并返回一维坐标 calType y(void)const { return loc.second; } //返回二维坐标 calType y(const calType& c) { loc.second = c; return loc.second; }//修改并返回二维坐标 locat up(void)const { return { loc.first - 1, loc.second }; } locat down(void)const { return { loc.first + 1, loc.second }; } locat left(void)const { return { loc.first, loc.second - 1 }; } locat right(void)const { return { loc.first, loc.second + 1 }; } locat& operator()(const rowType& r, const calType& c) { x(r), y(c); return *this; } locat& operator()(const locat& oth) { return (*this)(oth.x(), oth.y()); } bool operator<(const locat& oth)const { return x() == oth.x() ? y() < oth.y() : x() < oth.x(); } bool operator==(const locat& oth)const { return x() == oth.x() && y() == oth.y(); } friend std::ostream& operator<<(std::ostream& o, const locat& l) { o << '(' << l.x() << ',' << l.y() << ')'; return o; } private: std::pair<rowType, calType> loc; }; class Maze { public: using rowType = locat::rowType; using calType = locat::calType; using locats = std::vector<locat>; enum blockType { wall, road, way }; Maze(const locat& l) :xyMsg(l), Map(l.x(), mazeLine(l.y(), wall)) {} Maze(rowType row, calType cal); // 随机生成一个迷宫,采用Prim算法 std::function<locat(const locat& l)> operat[4]{ [](const locat& l) {return l.up(); }, [](const locat& l) {return l.down(); }, [](const locat& l) {return l.left(); }, [](const locat& l) {return l.right(); }, }; auto& operator()(const rowType& r,const calType& c) { return Map[r][c]; } auto& operator()(const locat& p) { return (*this)(p.x(), p.y()); } rowType row(void) { return xyMsg.x(); } // 返回迷宫的行数 calType cal(void) { return xyMsg.y(); } // 返回迷宫的列数 locat& start(void) { return _start; } locat& end(void) { return _end; } void show(const blockpic pic = block); // 打印迷宫 private: using mazeLine = std::vector<blockType>; // 单行迷宫 using mazeMap = std::vector<mazeLine>; // 迷宫图 locats findWall(const locat& p); //返回一个路周围的墙 locats findRoad(const locat& p); //返回一个墙周围的路 locat xyMsg; mazeMap Map; locat _start, _end; }; //给出迷宫问题的解决方案 class Solute :public Maze { public: Solute(const rowType& r, const calType& c) :Maze(r, c) { rowType tmpR; calType tmpC; show(); std::cout << std::endl << std::endl << "请输入起点的行坐标与列坐标:"; std::cin >> tmpR >> tmpC; (*this)(end()(tmpR, tmpC)) = way; std::cout << "请输入终点的行坐标与列坐标:"; std::cin >> tmpR >> tmpC; (*this)(start()(tmpR, tmpC)) = way; solve(start()); show(); std::cout << std::endl << std::endl; showWay(); } bool isIn(const locat& p) { return p.x() < row() && p.y() < cal(); } bool solve(const locat& p); void showWay(void) { if (!ans.empty()) { std::cout << ans.top(); ans.pop(); if (!ans.empty()) std::cout << " -> "; showWay(); } }; private: Maze mark{ locat{row(),cal()} }; jmc::Stack<locat> ans{}; }; }
Maze.cpp:
#include "Maze.h" jmc::Maze::Maze(rowType row, calType cal) :xyMsg(2 * row + 1, 2 * cal + 1), Map(2 * row + 1, mazeLine(2 * cal + 1, wall)) { // 初始化随机数生成器 static std::random_device rd; static std::default_random_engine e(rd()); static std::uniform_int_distribution<> d; std::map<blockType, std::set<locat>> mark{ {wall,{}},{road,{}} }; for (rowType i = 1; i < row * 2 + 1; i += 2) { for (calType j = 1; j < cal * 2 + 1; j += 2) { (*this)(i,j) = road; } } //随机生成起点,把边框分为四段 auto i = d(e, decltype(d)::param_type{ 0,3 }); auto j = i % 2 ? d(e, decltype(d)::param_type{ 0,(int)row - 2 }) : d(e, decltype(d)::param_type{ 0,(int)cal - 2 }); switch (i) { case 0: _start(j, 0); break; case 1: _start(0, j - 1); break; case 2: _start(row - 1, j); break; case 3: _start(j + 1, cal - 1); break; } _start(_start.x() * 2 + 1, _start.y() * 2 + 1); //将起点对应到实际位置 locats tmpRoad{ _start }; locats tmpWall = findWall(_start); mark[road].insert(tmpRoad.begin(), tmpRoad.end()); mark[wall].insert(tmpWall.begin(), tmpWall.end()); while (!mark[wall].empty()) { auto it = mark[wall].begin(); std::advance(it, d(e, decltype(d)::param_type{ 0,(int)mark[wall].size()-1 })); tmpRoad = findRoad(*it); //随机将一个wall集合中的元素传入findRoad auto s1 = mark[road].size(); //插入set前set大小 bool flag = false; for (auto& i : tmpRoad) { mark[road].insert(i); if (s1 != mark[road].size()) { s1 = mark[road].size(); tmpWall = findWall(i); mark[wall].insert(tmpWall.begin(), tmpWall.end()); flag = true; } } //若size有变化,表示此wall周围的road有未标记的,将此wall置为road if (flag) { mark[road].insert(*it); (*this)(*it) = road; } mark[wall].erase(it); } _end(tmpRoad.back()); } void jmc::Maze::show(const blockpic pic) { size_t m{}, n{}; for (const auto& i : Map) { for (const auto& j : i) { std::cout << pic[j]; } std::cout << m++ << std::endl; } for (size_t i = 0; i < cal(); printf("%2d", i++)); } jmc::Maze::locats jmc::Maze::findWall(const locat& p) { locats ret; locat tmp; if (p.x() != 1) { tmp = p.up(); if ((*this)(tmp) == wall) ret.push_back(tmp); } if (p.y() != 1) { tmp = p.left(); if ((*this)(tmp) == wall) ret.push_back(tmp); } if (p.x() != row() - 2) { tmp = p.down(); if ((*this)(tmp) == wall) ret.push_back(tmp); } if (p.y() != cal() - 2) { tmp = p.right(); if ((*this)(tmp) == wall) ret.push_back(tmp); } return ret; } jmc::Maze::locats jmc::Maze::findRoad(const locat& p) { assert(p.x() != 0 && p.x() != row() && p.y() != 0 && p.y() != cal()); locats ret; locat tmp; for (auto& i : operat) { tmp = i(p); if ((*this)(tmp) == road) ret.push_back(tmp); } return ret; } bool jmc::Solute::solve(const locat& p) { if (p == end()) return true; mark(p) = road; (*this)(p) = way; ans.push(p); for (auto& i : operat) { auto tmp = i(p); if (isIn(tmp) && (*this)(tmp) != wall && mark(tmp) != road && solve(tmp)) { return true; } } ans.pop(); mark(p) = wall; (*this)(p) = road; return false; }
主函数文件(测试用):
#include"Maze.h" int main(int argc, char* argv[]) { jmc::Solute s(30, 30); return 0; }
运行截图:
输出解决路径:
当然这里也可以写成展示每一步走的动画的样子,加个延时与清屏就可以了这里就不演示了。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
上一篇: C语言实现简单的扫雷游戏
下一篇: C语言学生成绩管理系统课程设计word版
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25