用Python制作迷宫图表

Question

嘿，我想用Python中的字典来绘制一个图表。我正在使用包含迷宫（b代表墙，a代表路径）的txt文件，并尝试创建一个列表字典，列出在迷宫中可行的所有走法（简单步骤，而不是完整路径）。你有任何关于我应该从哪里开始的想法吗？我以前从未使用过字典。

非常感谢您的帮助，这让我有了一个很好的开始。只有一个问题，我从一个有效的房子开始检查所有可能的路径。之后我将不得不移动到另一个房子并检查那里的路径。如何确保我不会陷入无限循环或重新检查已经检查过的房子？

- Daymor

---

请每个问题只提一个问题。在回答已经发布后编辑您的问题以包含新问题是很烦人的。 - Lightness Races in Orbit

Answer 1

假设迷宫看起来像一个网格，迷宫中的位置可以表示为元组（行，列）。构建字典时，为迷宫中的每个位置创建一个条目，初始值为空列表。在迷宫中的每个有效位置（r，c）处，确定是否可以到达（r-1，c），（r，c-1），（r+1，c）和（r，c+1）。如果可以，则将该元组添加到列表中。因此，假设我可以从（r，c）到达（r-1，c）和（r，c+1），则字典中的条目如下所示

  maze_dict[(r,c)] = [(r-1,c), (r,c+1)]

创建一个空字典，需要使用以下代码：

代码演示：

maze_dict = {}

你还应该查看Python教程中字典部分的内容。

- seggy

---

关于字典的快速问题，我能否获取可能的方式列表并添加到字典中？而且我不能“附加”键的值？ - Daymor

如果你得到了可能的方式列表，那么你可以迭代地将它们添加到字典中。在字典中，你不能修改一个键的值，因为这会破坏哈希。 - seggy

Daymor：你只需向字典中写入键/值对。你可以放置任意多个这样的键/值对。 - Paul McMillan

我已经编写了如何获取一个房子可能的移动方式的代码。我的问题是，我要如何检查所有这些移动方式而不重复？ - Daymor

检查所有它们是为了什么？一时之间，您可以将标志与每个移动相关联。如果设置了标志，则表示您以前已经看过该位置，如果没有，则表示它是唯一的。 - seggy

Answer 2

非常感谢您的帮助，这让我有了一个很好的开始。只有一个问题，我从一个有效的房子开始，检查所有可能的路径。之后我必须移动到另一个房子并检查那里的路径。如何确保我不会陷入无限循环或重新检查已经检查过的房子？

创建一个“House”类，包括其网格坐标：

class House(object):
    def __init__(self, pos):
        self.pos = pos # the coordinates (position) on the grid, a tuple
        self.paths = [] # Empty array to hold paths

创建一些房屋：

houses = [House((1,3)), House((3,3)), House((4,3))] # a list of houses

现在，逐个检查每个房子，并计算它的路径（或路径）

paths = {}
paths[(1,3)] = [(2,3), (4,3) ... ] # possible paths to the point (1,3)

for i in houses:
    try:
       i.paths = paths[(i.pos)]
    except KeyError:
       print "I don't know how to get to ", i.pos

按顺序遍历列表可以确保每个房子只被检查一次。现在你可以找出那些无法到达的房子：

for i in houses:
   if not i.paths:
      print "I did not find a way to reach the house at ",i.pos

- Burhan Khalid