数据结构实验课要求解决一个迷宫问题，这里给定长宽用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