- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++ DFS算法实现走迷宫自动寻路由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
C++ DFS算法实现走迷宫自动寻路,供大家参考,具体内容如下 。
事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. 。
深度优先搜索算法是在我在图的部分接触到的,后来才发现它也可以不用在图的遍历上,它是一个独立的算法,它也可以直接用在一个二维数组上.
其算法原理和实现步骤在代码中已经有了很好的体现了,这里就不再赘述.
在程序中实现了手动操控走迷宫和自动走迷宫两种模式,并且可在自动走完迷宫后显示行走的路径.
如果要修改程序使用的迷宫地图只需要修改map二维地图数组和两个地图宽高的常量值即可。同样可以使用自动走迷宫的模式.
理论上这种算法可以对任意大小任意复杂的迷宫搜索路径,但是因为这种算法是用递归实现的,占用空间较大,地图大小增大也会多使用很多的空间,受限于堆栈空间的限制我在把地图大小增加到2020的时候运行自动寻路模式就会报堆栈溢出异常了。我在代码准备了1818和15*15的两个迷宫地图二维数组用于测试.
Windows VS2019 。
Game.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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
|
#pragma once
#include <iostream>
#include <map>
#include <conio.h>
#include <vector>
#include <windows.h>
using
namespace
std;
//地图宽高常量
constexpr unsigned
int
mapWidth = 18;
constexpr unsigned
int
mapHeight = 18;
//游戏类
class
Game
{
private
:
map<
int
, string> cCMAEMap;
//地图数组元素对应字符
map<
char
,
int
*> movDistanceMap;
//按键对应移动距离
int
px, py;
//玩家坐标
int
dArr[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
//数值和移动方向对应数组
vector<
int
*> tempPathVec;
//路径向量
vector<vector<
int
*>> allPathVec;
//存储所有路径向量
//检查参数位置是否可走
bool
check(
int
x,
int
y,
int
(*map)[mapWidth])
{
//判断修改后的玩家坐标是否越界、修改后的玩家坐标位置是否可走
if
(x < 0 || x >= mapWidth || y < 0 || y >= mapHeight || (map[y][x] != 0 && map[y][x] != 3))
return
false
;
return
true
;
}
//控制玩家移动函数
bool
controlMove (
int
(*map)[mapWidth])
{
//键盘按下时
if
(!_kbhit())
return
false
;
char
key = _getch();
if
(key !=
'w'
&& key !=
's'
&& key !=
'a'
&& key !=
'd'
)
return
false
;
int
temp_x = px, temp_y = py;
//临时记录没有改变之前的玩家坐标
px += movDistanceMap[key][0];
py += movDistanceMap[key][1];
//如果位置不可走则撤销移动并结束函数
if
(!check(px, py, map))
{
px = temp_x, py = temp_y;
return
false
;
}
//判断是否已到达终点
if
(map[py][px] == 3)
{
//打印信息并返回true
cout <<
"胜利!"
<< endl;
return
true
;
}
map[temp_y][temp_x] = 0;
//玩家原本的位置重设为0路面
map[py][px] = 2;
//玩家移动后的位置设为玩家2
//清屏并打印修改后地图
system
(
"cls"
);
printMap(map);
return
false
;
}
//用对应图形打印地图
void
printMap(
int
(*map)[mapWidth])
{
for
(
int
i = 0; i < mapHeight; i++)
{
for
(
int
j = 0; j < mapWidth; j++)
cout << cCMAEMap[map[i][j]];
cout << endl;
}
}
//初始化map容器
void
initMapContainer()
{
//数组元素和字符对应
string cArr[4] = {
" "
,
"■"
,
"♀"
,
"★"
};
for
(
int
i = 0; i < 4; i++)
cCMAEMap.insert(pair <
int
, string>(i, cArr[i]));
//输入字符和移动距离对应
char
kArr[4] = {
'w'
,
's'
,
'a'
,
'd'
};
for
(
int
i = 0; i < 4; i++)
movDistanceMap.insert(pair <
char
,
int
*>(kArr[i], dArr[i]));
}
//找到玩家所在地图的位置
void
findPlayerPos(
const
int
(*map)[mapWidth])
{
for
(
int
i = 0; i < mapHeight; i++)
for
(
int
j = 0; j < mapWidth; j++)
if
(map[i][j] == 2)
{
px = j, py = i;
return
;
}
}
//深度优先搜索
void
dfs(
int
cx,
int
cy,
int
(*map)[mapWidth])
{
//把当前玩家位置插入到数组
tempPathVec.push_back(
new
int
[2] {cx, cy});
//循环四个方向上下左右
for
(
int
i = 0; i < 4; i++)
{
int
x = cx + dArr[i][0];
//玩家下一个位置的坐标
int
y = cy + dArr[i][1];
//检查下一个位置是否可走
if
(!check(x, y, map))
continue
;
if
(map[y][x] == 3)
//已到达终点
{
tempPathVec.push_back(
new
int
[2]{ x, y });
//把终点位置插入到向量中
allPathVec.push_back(tempPathVec);
return
;
}
//为普通路径
else
{
map[cy][cx] = -1;
//当前位置临时设为-1,递归搜索时不可走原路,非0且非3的位置都不可走
dfs(x, y, map);
//用下一个位置作为参数递归
map[cy][cx] = 0;
//递归完成后将当前位置重设为0,可走路径
}
}
//最后没有找到可走的路径则删除向量最后一个元素,此时函数结束递归退回到上一层
tempPathVec.pop_back();
}
//输出路径信息
void
printPathInformation()
{
//int minSizePathIndex = 0; //记录最短路径在路径向量中的下标
//for (int i = 0; i < allPathVec.size(); i++)
//{
// cout << allPathVec.at(i).size() << " ";
// if (allPathVec.at(i).size() < allPathVec.at(minSizePathIndex).size())
// minSizePathIndex = i;
//}
//cout << endl << "最小长度:" << allPathVec.at(minSizePathIndex).size() << endl;
输出最短路径信息
//for (auto dArr2 : allPathVec.at(minSizePathIndex))
// cout << dArr2[0] << "_" << dArr2[1] << " ";
//输出所有路径信息
//for (auto arr : allPathVec)
//{
// for (auto dArr2 : arr)
// cout << dArr2[0] << "__" << dArr2[1] << " ";
// cout << endl;
//}
}
//寻找路径
int
findPath(
int
(*map)[mapWidth])
{
findPlayerPos(map);
//找到玩家所在地图中的位置
//如果多次调用findPaths函数,则需要先清除上一次调用时在向量中遗留下来的数据
tempPathVec.clear();
allPathVec.clear();
dfs(px, py, map);
//找到所有路径插入到allPathVec
//找到最短路径在allPathVec中的下标
int
minSizePathIndex = 0;
//记录最短路径在路径向量中的下标
for
(
int
i = 0; i < allPathVec.size(); i++)
{
if
(allPathVec.at(i).size() < allPathVec.at(minSizePathIndex).size())
minSizePathIndex = i;
}
return
minSizePathIndex;
}
//显示路径
void
showPath(
int
(*map)[mapWidth], vector<
int
*> tempPathVec)
{
//将能找到的最短的路径上的元素赋值全部赋值为2并输出
for
(auto tempDArr : tempPathVec)
map[tempDArr[1]][tempDArr[0]] = 2;
system
(
"cls"
);
printMap(map);
//打印地图
}
//手动模式
void
manualMode(
int
(*map)[mapWidth])
{
while
(!controlMove(map))
//游戏循环
Sleep(10);
}
//自动模式
void
automaticMode(
int
(*map)[mapWidth])
{
//找到最短路径
vector<
int
*> tempPathVec = allPathVec.at(findPath(map));
for
(
int
i = 1; i < tempPathVec.size(); i++)
{
map[tempPathVec[i - 1][1]][tempPathVec[i - 1][0]] = 0;
map[tempPathVec[i][1]][tempPathVec[i][0]] = 2;
system
(
"cls"
);
printMap(map);
//打印地图
Sleep(200);
}
cout <<
"胜利!是否打印完整路径?(Y / N)"
<< endl;
char
key = _getch();
if
(key ==
'Y'
|| key ==
'y'
)
showPath(map, tempPathVec);
}
public
:
//构造
Game(
int
(*map)[mapWidth],
char
mode)
{
initMapContainer();
//初始化map容器
findPlayerPos(map);
//找到玩家所在地图中的位置
system
(
"cls"
);
printMap(map);
//先打印一遍地图 ♀ ■ ★
(mode ==
'1'
) ? manualMode(map) : automaticMode(map);
}
//析构释放内存
~Game()
{
for
(auto it = tempPathVec.begin(); it != tempPathVec.end(); it++)
{
delete
* it;
*it = nullptr;
}
tempPathVec.clear();
//这里不会释放allPathVec了
allPathVec.clear();
}
};
|
迷宫.cpp main函数文件 。
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
|
#include "Game.h"
//光标隐藏
void
HideCursor()
{
CONSOLE_CURSOR_INFO cursor_info = { 1, 0 };
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}
int
main()
{
HideCursor();
//光标隐藏
//0空地,1墙,2人, 3出口
//int map[mapHeight][mapWidth] = {
// 2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1,
// 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1,
// 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0,
// 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1,
// 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
// 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0,
// 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0,
// 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1,
// 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,
// 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0,
// 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1,
// 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1,
// 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
// 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0,
// 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 3,
//};
int
map[mapHeight][mapWidth]
{
2, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1,
0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1,
1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0,
1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0,
1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1,
0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1,
0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1,
1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0,
0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1,
1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1,
1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0,
0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1,
0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1,
1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0,
1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 3,
};
//复制一个一样的数组以保证重新开始游戏时可以重置数组
int
mapCopy[mapHeight][mapWidth];
memcpy
(mapCopy, map,
sizeof
(mapCopy));
while
(
true
)
{
cout <<
"选择模式:1,手动 2,自动"
<< endl;
char
key = _getch();
Game game(mapCopy, key);
//进入游戏
cout <<
"输入r重新开始:"
<< endl;
key = _getch();
if
(key !=
'r'
&& key !=
'R'
)
//输入值不为r则结束程序
break
;
memcpy
(mapCopy, map,
sizeof
(mapCopy));
//重新赋值
system
(
"cls"
);
}
return
0;
}
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我.
原文链接:https://blog.csdn.net/qq_46239972/article/details/107387149 。
最后此篇关于C++ DFS算法实现走迷宫自动寻路的文章就讲到这里了,如果你想了解更多关于C++ DFS算法实现走迷宫自动寻路的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我想递归地遍历一个目录,但我希望 python 在遇到包含超过 100 个文件的目录时从任何单个 listdir 中断。基本上,我正在搜索 (.TXT) 文件,但我想避免使用包含大型 DPX 图像序列
我正在尝试遍历列表(例如 sql 行)并为每一行触发例程。问题是传递给函数的值不会在运行时进行评估,因此根据函数执行所需的时间,它可能会使用下一行中的任何值而不是当前行。 我知道我可以在普通函数中提取
我需要以毫秒为单位的时间来处理大量事务,因此我想要正确且快速的东西。下面的工作会做得最好吗? : iMilli := int((time.Nanoseconds() % 1e6) / 1e3
我有以下目录/文件设置(已简化): Ce +---top.txt +---X0.0 | | | +---Y0.0 | | | | |
我遇到了类似的问题: Connecting to Redis To Go with PHP 基本上,我在 redis 中有这个 uri: redis://myusername:foopassword@
我阅读了下面的主题 Go: multiple value in single-value context 但我不明白这个解释在我的案例中。可能是因为我想使用 interface 在下面的情况下,我得到
我有一个模板,我想使用 text/template 评估各个字段包裹。我很难弄清楚评估应该如何工作,因为下面的代码似乎失败了。模板包是否足够强大以处理此类评估? type something stru
我编写了简单的服务器程序来从客户端接收数据。我有点不明白有时我从函数中得到错误 read tcp4 IP:PORT i/o timeoutint, err := conn.Read([]byte) 未
我只需要解码和更新 json 对象的特定值。问题是我不知道对象的完整结构。 encoding/json 包“忽略”/截断结构中未提供的字段,因此在编码时这些字段将丢失。 我想知道是否可以只解码我知道的
我正在尝试使用带有 C++ 目标的 ANTLR4 来实现 TSql 解析器。我抓取了语法文件 here .该jar用于制作相应的源文件(因冲突将TSqlParser.cpp中的NULL全部改为null
我在 win7 中使用 python 3.3.3 - 我只想列出网络目录中的所有文件。 import os for root, dirs, files in os.walk("X:\\network\
当我运行 go 脚本 ( go run example.go ) 时出现此错误 /home/travis/.gvm/gos/go1.1.2/src/pkg/github.com/user/exampl
我正在尝试通过 gmail API 发送电子邮件使用 Go但我发现文档非常有缺陷/令人困惑。这一次我看不到收据字段和电子邮件正文。 我不需要上传任何东西,所以我找到了 Simple upload ,
本人是一名专业的windows/.Net开发者,一直在慢慢学习rails/ruby/python/etc。在我有空的时候。在过去 8 年左右的时间里,我也一直在使用各种 Linux 发行版。然而,有一
我想知道是否可以使用 std http 来响应 http 请求打包并仍然保持 go 例程事件(例如运行任务密集型任务)。用例是我需要接收一个 http 请求,然后在几分钟后回调该服务 最佳答案 只需从
我想知道关于指针的最佳实践是什么。我应该在结构上还是在其字段上定义它们。我虽然定义一个指向结构本身的指针是有意义的,但这里有一个我觉得很有趣的例子。如果所有字段都是指针,为什么我不应该使用指向整个结构
我是一名优秀的程序员,十分优秀!