如何使用Python计算迷宫中的死胡同（又称死胡同）？
问题描述 投票：0回答：1
问题陈述
我正在开发一个迷宫解决程序，我需要计算死胡同（也称为死胡同）的数量。迷宫的表示方式允许识别不同的路径和交叉点。
尝试过的方法
- 标记路径：最初，我用“X”标记了大门和死胡同之间的所有节点，然后标记了从一个大门到另一个大门的所有可能路线。 （迄今为止最好的一个，但不能概括所有测试用例）
- 使用交叉点：我尝试使用具有多个开口的节点作为潜在的死胡同标识符。
附加信息
- 广度优先搜索（BFS）：我目前正在使用 BFS 遍历迷宫中的所有节点，但我很难正确识别和计算死胡同。
- 迷宫由 0 和 1 表示（0 = 路，1 = 墙）。
问题
我可以使用哪些方法来使用 Python 来计算迷宫中的死胡同？我正在寻找可以简化此过程的算法建议或 Python 库。
迷宫样本
迷宫有 8 个可通行的死胡同。访问由三角形表示
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]]
1个回答
0
投票
投票
请注意，用于表示迷宫的代码与您的绘图并不完全对应（代码中的厚墙，绘图中的薄墙）。 尽管如此，我还是很有趣地实现了一个迷宫类，该类从“厚墙”数据中提取“薄墙”迷宫；我添加了一种列出死胡同的方法（我的意思是实际的死胡同，而不是您在绘图上标记的入口），一种用于切割通向死胡同的迷宫分支的方法，以及另一种用于切割所有死胡同的方法-结束分支，只留下（在简单迷宫中）正确的路径。
这并不完全符合您的要求（计算入口数），但由于您的问题有点模糊，这是我能做的最好的事情。您始终可以在我的基础上构建其他方法来满足您的需求：
from copy import deepcopy
class Maze:
def __init__(self, data):
self.data = data
self.work_data = deepcopy(data)
self.height = len(data) // 2
self.width = len(data[0]) // 2
self.exit_dict = {
(-1, 0): 'N',
(1, 0): 'S',
(-0, -1): 'W',
(0, 1): 'E',
}
self.offset_dict = {e: o for o, e in self.exit_dict.items()}
opposite_dict = {
'N': 'S',
'S': 'N',
'W': 'E',
'E': 'W',
}
def node_exits(self, x, y, work=False):
data = self.work_data if work else self.data
if not all((0 <= x <= self.width, 0 <= y <= self.height)):
raise Exception("Out of bounds")
exits = []
for offset, direction in self.exit_dict.items():
if not data[2 * y + 1 + offset[0]][2 * x + 1 + offset[1]]:
exits.append(direction)
return exits
def node_repr(self, x, y, work=False):
ne = self.node_exits(x, y, work)
return(
f' {" | " if "N" in ne else " "} ',
f'{"---" if "W" in ne else " "}{" x " if len(ne) == 1 else " o "}{"---" if "E" in ne else " "}',
f' {" | " if "S" in ne else " "} ')
def node_print(self, x, y, work=False):
print('\n'.join(self.node_repr(x, y, work)))
def __repr__(self, work=False):
return '\n'.join(
'\n'.join(
''.join(
self.node_repr(x, y, work)[i]
for x in range(self.width)
)
for i in range(3)
)
for y in range(self.height)
)
def show_work_state(self):
print(self.__repr__(True))
def dead_ends(self, work=False):
return [(x, y) for x in range(self.width) for y in range(self.height) if len(self.node_exits(x, y, work)) == 1]
def cut_dead_end(self, x, y):
ne = self.node_exits(x, y, work=True)
if len(ne) != 1:
return
offset = self.offset_dict[ne[0]]
self.work_data[2 * y + 1 + offset[0]][2 * x + 1 + offset[1]] = 1
self.cut_dead_end(x + offset[1], y + offset[0])
def trim_maze(self):
while de := self.dead_ends(True):
self.cut_dead_end(*de[0])
示例：
a = Maze([
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
])
print(a)
o ------ o ------ o ------ o ------ o ------ o ------ o ------ o ------ o x
| | | | |
| | | | |
o ------ o ------ o o o ------ o o ------ o o ------ o
| | | | |
| | | | |
x o ------ o x o ------ o x o ------ o ------ o
| | | | |
| | | | |
o ------ o o ------ o ------ o o ------ o o ------ o o
| | | | |
| | | | |
o ------ o ------ o ------ o ------ o ------ o o ------ o o ------ o
| | | | |
| | | | |
o ------ o o o ------ o o x ------ o ------ o ------ o
| | | | |
| | | | |
o ------ o x o o ------ o o ------ x o ------ o
| | | | |
| | | | |
--- o o ------ o o o ------ x o ------ o o ------ o
| | | | | |
| | | | | |
o o o ------ o o ------ o ------ o ------ o x o
| | | | |
| | | | |
x o ------ o ------ o ------ o x ------ o ------ o ------ o ------ o
|
print(a.dead_ends())
# [(0, 2), (0, 9), (2, 6), (3, 2), (5, 7), (5, 9), (6, 2), (6, 5), (7, 6), (8, 8), (9, 0)]
a.cut_dead_end(0, 2)
a.show_work_state()
o o o o ------ o ------ o ------ o ------ o ------ o x
| | | |
| | | |
o o o o o ------ o o ------ o o ------ o
| | | |
| | | |
o o o x o ------ o x o ------ o ------ o
| | |
| | |
o o o ------ o ------ o o ------ o o ------ o o
| | | | |
| | | | |
o ------ o ------ o ------ o ------ o ------ o o ------ o o ------ o
| | | | |
| | | | |
o ------ o o o ------ o o x ------ o ------ o ------ o
| | | | |
| | | | |
o ------ o x o o ------ o o ------ x o ------ o
| | | | |
| | | | |
--- o o ------ o o o ------ x o ------ o o ------ o
| | | | | |
| | | | | |
o o o ------ o o ------ o ------ o ------ o x o
| | | | |
| | | | |
x o ------ o ------ o ------ o x ------ o ------ o ------ o ------ o
|
a.trim_maze()
a.show_work_state()
o o o o o o o o o o
o o o o o o o o o o
o o o o o ------ o o o o o
| |
| |
o o o ------ o ------ o o ------ o o o o
| |
| |
o ------ o ------ o o o o o ------ o o o
| |
| |
o ------ o o o o o o o ------ o ------ o
| |
| |
o ------ o o o o o o o o ------ o
| |
| |
--- o o o o o o o o o ------ o
|
|
o o o o o o o o o o
|
|
o o o o o o o ------ o ------ o ------ o
|
最新问题
- 从材料描述列中提取子字符串的特定模式
- 我该如何解决“无法解析配置'：app：debugRuntimeClasspath'的所有文件”
- Zoho PostMessage API 返回 1108 域未注册
- 更改 Elementor 菜单购物车小部件中的文本
- Flutter - 无法通过带有 firebase_code 包的 cocoapods 1.15.2 运行？
- 列在 Azure devOps 查询中返回空值
- 单击按钮时更改对话框内的按钮属性
- 我的项目引导安装发生了什么？
- 发现问题：功能不符合在后台访问位置的条件
- 业务流程模型与流程流程图
- 用另一个数组初始化对象的 const 数组
- JS 错误：未捕获类型错误：“.year-link”。click 不是函数
- UML 类图 - 关于解释和组合的问题
- 发布自己的私有Android库到自己的gitlab
- 输入时在 Swiftui 文本字段中设置货币格式
- 升级到 pac4j v5 时的集中注销行为
- Spring 启动 WebClient 连接由于 io.netty.handler.codec.TooLongFrameException 而被冻结：HTTP 标头大于 8192 字节
- 无法读取未定义的属性（读取“templates_empty_title”）
- .NET - 服务总线 - 将消息移动到 DLQ
- 今天java类讨论call是一个Data类型怎么样？ [已关闭]
© www.soinside.com 2019 - 2024. All rights reserved.