个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
38
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C语言使用深度优先搜索算法解决迷宫问题(堆栈)由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
本文实例讲述了C语言使用深度优先搜索算法解决迷宫问题。分享给大家供大家参考，具体如下:
深度优先搜索 。
伪代码 。
（Pseudocode）如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
将起点标记为已走过并压栈;
while (栈非空) {
从栈顶弹出一个点p;
if (p这个点是终点)
break;
否则沿右、下、左、上四个方向探索相邻的点
if (和p相邻的点有路可走，并且还没走过)
将相邻的点标记为已走过并压栈，它的前趋就是p点;
}
if (p点是终点) {
打印p点的坐标;
while (p点有前趋) {
p点 = p点的前趋;
打印p点的坐标;
}
} else
没有路线可以到达终点;
|
C语言代码:
|
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
|
#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
struct
point {
int
row, col; } stack[512];
int
top = 0;
void
push(
struct
point p)
{
stack[top++] = p;
}
struct
point pop(
void
)
{
return
stack[--top];
}
int
is_empty(
void
)
{
return
top == 0;
}
int
maze[MAX_ROW][MAX_COL] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
void
print_maze(
void
)
{
int
i, j;
for
(i = 0; i < MAX_ROW; i++) {
for
(j = 0; j < MAX_COL; j++)
printf
(
"%d "
, maze[i][j]);
putchar
(
'\n'
);
}
printf
(
"*********\n"
);
}
struct
point predecessor[MAX_ROW][MAX_COL] = {
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
{{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}},
};
void
visit(
int
row,
int
col,
struct
point pre)
{
struct
point visit_point = { row, col };
maze[row][col] = 2;
predecessor[row][col] = pre;
push(visit_point);
}
int
main(
void
)
{
struct
point p = { 0, 0 };
maze[p.row][p.col] = 2;
push(p);
while
(!is_empty()) {
p = pop();
if
(p.row == MAX_ROW - 1
/* goal */
&& p.col == MAX_COL - 1)
break
;
if
(p.col+1 < MAX_COL
/* right */
&& maze[p.row][p.col+1] == 0)
visit(p.row, p.col+1, p);
if
(p.row+1 < MAX_ROW
/* down */
&& maze[p.row+1][p.col] == 0)
visit(p.row+1, p.col, p);
if
(p.col-1 >= 0
/* left */
&& maze[p.row][p.col-1] == 0)
visit(p.row, p.col-1, p);
if
(p.row-1 >= 0
/* up */
&& maze[p.row-1][p.col] == 0)
visit(p.row-1, p.col, p);
print_maze();
}
if
(p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
{
printf
(
"(%d, %d)\n"
, p.row, p.col);
while
(predecessor[p.row][p.col].row != -1) {
p = predecessor[p.row][p.col];
printf
(
"(%d, %d)\n"
, p.row,
p.col);
}
}
else
printf
(
"No path!\n"
);
return
0;
}
|
希望本文所述对大家C语言程序设计有所帮助.
原文链接：http://blog.csdn.net/e421083458/article/details/39185171 。
最后此篇关于C语言使用深度优先搜索算法解决迷宫问题(堆栈)的文章就讲到这里了,如果你想了解更多关于C语言使用深度优先搜索算法解决迷宫问题(堆栈)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
38
4
0
假设您已经用 Python 编写了一个 m x n 矩阵。矩阵之外的值是不可能的。假设你是在矩阵中移动的东西(就像在迷宫中)并且你不能跨越边界。当您在迷宫中移动时，您会不断考虑您的选择，您可以走哪条路
我正在实现随机鼠标算法来探索迷宫。一段时间后，算法陷入无限循环。我调试了一下，它似乎在一条 channel 之间来回卡住了。 请看一下我的算法实现。 这是我的代码:方向是相对于机器人的。 public
我有一个用 java 编写的工作 ascii 迷宫解算器，使用 char 数组，它将正确路径的每个位置设置为前一个位置 + 1。我使用以下代码来从中获取正确路径，但是它仅适用于垂直运动。任何有关此事的
我有一个生成随机迷宫的程序。迷宫中会显示一个红点，并且迷宫中的每个方 block 都会闪烁红点。迷宫中的所有 block 都是 == 1，如果红点穿过该 block ，它就会递增++。红点朝最小数字的
已关闭。此问题需要 debugging details 。目前不接受答案。 编辑问题以包含 desired behavior, a specific problem or error, and the
我创建了一个从文本文件上传的迷宫，该迷宫当前在运行时完全可见且功能正常。但是，我只想将播放的路线显示为可见，因此仅使起始位置和周围的墙壁/地板在开始时可见。有人知道该怎么做吗？ 以下是 Board 类
起初我觉得这很容易，但是当我开始做的时候，我不知道如何继续下去了。我的想法是使用面板，然后绘制粗线，但是绘制墙壁并使我的角色不会超出这些墙壁的正确方法是什么？我无法想象我怎么可能做到这一点。这是一个迷
我从一个文件中得到了一个迷宫，我尝试使用一个程序编写一个类Exercise4，该程序将这样的迷宫文件读入二维 boolean 数组。然后在控制台上显示该数组，每一行一行。使用空白符号和 # 符号表示数
如何通过光栅图像数据找到非线性路径？例如，最低成本算法？起点和终点已知，并给出如下: 起点 = (0,0) 终点 = (12,-5) 例如，通过(灰度)光栅图像提取蜿蜒河流的近似路径。 # fake
在我的游戏中，玩家在迷宫中导航。我不知道如何与墙壁进行正确的碰撞检测。停留在某个区域很容易进行碰撞检测: if (x > rightWallX - playerWidth) x = rightWall
基本上，我一直在按照 Java 教程制作一个基本的迷宫游戏，其中我生成一个随机迷宫，并将其保存到文件中，然后使用 Jpanel 将其打印出来，但是在编译时我不断收到此错误。 Exception in
注意:这是 MSVC，C++17 问题。 免责声明:我知道有人尝试过，是的，我试图找到相关的 SO 答案。 我可以编码 UDL , 以实现将数字文字转换为 std::array，在编译时: /
我目前正在开发一个随机迷宫生成器，它将迷宫存储在一个名为 grid 的二维数组中。这将在稍后用于生成一个真正的 3D 迷宫，用户随后可以穿过该迷宫。 在做了一些研究之后，我尝试使用递归除法算法创建这个
题目地址：https://leetcode-cn.com/problems/the-maze-ii/ 题目描述 There is a ball in a maze with empty space
我正在尝试用 python 编写脚本来解决一种具有多个起点和多个终点的迷宫。正确的路径是从起点沿着直线前进。 例如一个有 4 条路径的迷宫: 起初我想使用左手/右手规则，但由于迷宫的特点，它没有太大意
我正在尝试在 opengl 中创建一个简单的 3D 迷宫。我最初的想法是有一个立方体网格，每个立方体的一些面是透明的(用于走廊)。但是，我在想出一种有效执行此操作的方法时遇到了一些麻烦。我不想为我的迷
我的 DFS 算法在解中缺少节点时遇到问题(检查图片)。每次我的算法遇到死胡同时都会发生这种情况:节点从堆栈中弹出并返回，直到找到可用的移动，并且再也不会重新包含在内。有没有一种简单的方法可以在不重新
所以我正在用 Java 构建 pacman 游戏来自学游戏编程。 我有一个基本的游戏窗口，其中绘制了吃 bean Sprite 和幽灵 Sprite ，吃 bean 使用箭头键移动，不会超出窗口的墙壁
我使用的代码只是取自一个示例，它确实为我的场景建了一堵墙: /** This loop builds a wall out of individual bricks. */ public vo
我正在从事一个包含这些条件的学校元素: 只使用 JS、HTML5 和 CSS 制作迷宫。 在 Angular 色周围制作 torch 效果。你不能穿墙照明。 我开始使用 Canvas 制作这款游戏
我是一名优秀的程序员,十分优秀！