个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
24
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章Python使用回溯法子集树模板解决迷宫问题示例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
本文实例讲述了Python使用回溯法解决迷宫问题。分享给大家供大家参考，具体如下:
问题 。
给定一个迷宫，入口已知。问是否有路径从入口到出口，若有则输出一条这样的路径。注意移动可以从上、下、左、右、上左、上右、下左、下右八个方向进行。迷宫输入0表示可走，输入1表示墙。为方便起见，用1将迷宫围起来避免边界问题.
分析 。
考虑到左、右是相对的，因此修改为：北、东北、东、东南、南、西南、西、西北八个方向。在任意一格内，有8个方向可以选择，亦即8种状态可选。因此从入口格子开始，每进入一格都要遍历这8种状态.
显然，可以套用回溯法的子集树模板.
注意，解的长度是不固定的.
代码 。
|
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
|
# 迷宫（1是墙，0是通路）
maze
=
[[
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
],
[
0
,
0
,
1
,
0
,
1
,
1
,
1
,
1
,
0
,
1
],
[
1
,
1
,
0
,
1
,
0
,
1
,
1
,
0
,
1
,
1
],
[
1
,
0
,
1
,
1
,
1
,
0
,
0
,
1
,
1
,
1
],
[
1
,
1
,
1
,
0
,
0
,
1
,
1
,
0
,
1
,
1
],
[
1
,
1
,
0
,
1
,
1
,
1
,
1
,
1
,
0
,
1
],
[
1
,
0
,
1
,
0
,
0
,
1
,
1
,
1
,
1
,
0
],
[
1
,
1
,
1
,
1
,
1
,
0
,
1
,
1
,
1
,
1
]]
m, n
=
8
,
10
# 8行，10列
entry
=
(
1
,
0
)
# 迷宫入口
path
=
[entry]
# 一个解（路径）
paths
=
[]
# 一组解
# 移动的方向（顺时针8个：N, EN, E, ES, S, WS, W, WN）
directions
=
[(
-
1
,
0
),(
-
1
,
1
),(
0
,
1
),(
1
,
1
),(
1
,
0
),(
1
,
-
1
),(
0
,
-
1
),(
-
1
,
-
1
)]
# 冲突检测
def
conflict(nx, ny):
global
m,n,maze
# 是否在迷宫中，以及是否可通行
if
0
<
=
nx < m
and
0
<
=
ny < n
and
maze[nx][ny]
=
=
0
:
return
False
return
True
# 套用子集树模板
def
walk(x, y):
# 到达(x,y)格子
global
entry,m,n,maze,path,paths,directions
if
(x,y) !
=
entry
and
(x
%
(m
-
1
)
=
=
0
or
y
%
(n
-
1
)
=
=
0
):
# 出口
#print(path)
paths.append(path[:])
# 直接保存，未做最优化
else
:
for
d
in
directions:
# 遍历8个方向(亦即8个状态)
nx, ny
=
x
+
d[
0
], y
+
d[
1
]
path.append((nx,ny))
# 保存，新坐标入栈
if
not
conflict(nx, ny):
# 剪枝
maze[nx][ny]
=
2
# 标记，已访问（奇怪，此两句只能放在if区块内！）
walk(nx, ny)
maze[nx][ny]
=
0
# 回溯，恢复
path.pop()
# 回溯，出栈
# 解的可视化（根据一个解x，复原迷宫路径，'2'表示通路）
def
show(path):
global
maze
import
pprint, copy
maze2
=
copy.deepcopy(maze)
for
p
in
path:
maze2[p[
0
]][p[
1
]]
=
2
# 通路
pprint.pprint(maze)
# 原迷宫
print
()
pprint.pprint(maze2)
# 带通路的迷宫
# 测试
walk(
1
,
0
)
print
(paths[
-
1
],
'\n'
)
# 看看最后一条路径
show(paths[
-
1
])
|
效果图 。
希望本文所述对大家Python程序设计有所帮助.
原文链接：http://www.cnblogs.com/hhh5460/p/6919320.html 。
最后此篇关于Python使用回溯法子集树模板解决迷宫问题示例的文章就讲到这里了,如果你想了解更多关于Python使用回溯法子集树模板解决迷宫问题示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
24
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 制作这款游戏
我是一名优秀的程序员,十分优秀！