数据结构实验课要求解决一个迷宫问题，这里给定长宽用prime算法随机生成了一个迷宫并从指定起点与终点打印出了迷宫的解决方案，此处用到了栈数据结构，这里的jmc::Stack是我自己写的栈，这里就不放了，可以换成一切具有常规意义的empty、pop、push接口的栈ADT，或者直接使用std::stack就行，注意头文件的#include"Stack"也改一下
Maze.h:
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#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:
?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#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;
}
|
主函数文件（测试用）：
?| 1 2 3 4 5 6 |
#include"Maze.h"
int main(int argc, char* argv[])
{
jmc::Solute s(30, 30);
return 0;
}
|
运行截图：
输出解决路径：
当然这里也可以写成展示每一步走的动画的样子，加个延时与清屏就可以了这里就不演示了。
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：https://blog.csdn.net/J__M__C/article/details/111413412
如果您对该产品感兴趣，请填写办理（客服微信：xiaoxiongyidong）
发表评论
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。