所以，基本上，我试图编写一个解决迷宫的程序我用不同的迷宫做了很多测试，我意识到我的程序不能解决所有的迷宫，只有少数，因为有一些特定的死胡同，我的程序被卡住，不能回去。
我的代码背后的逻辑基本上是在迷宫中运行的东西，直到它找到出口，如果它在这个过程中找到一个死胡同，它应该能够返回并找到一条新的未探索的路径。
我的代码运行良好，直到我开始用更复杂的迷宫和不同类型的棘手死胡同来测试它。例如：
maze = (
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,1,0,0,0,0,0,1],
[1,1,1,0,1,1,1,0,1,0,1,0,1,0,1],
[1,1,1,0,1,0,1,0,1,0,1,1,1,0,1],
[1,1,1,1,1,0,1,0,1,0,0,1,0,0,1],
[1,1,0,0,0,0,1,0,1,1,0,1,0,1,1],
[1,1,0,1,1,0,0,0,0,1,0,1,0,1,1],
[1,1,0,0,1,1,0,1,0,1,0,1,0,0,1],
[1,1,0,1,0,0,1,0,0,0,1,0,0,1,1],
[1,1,1,1,1,1,1,1,1,1,1,3,1,1,1]
)
这是一个迷宫的例子，我的程序可以解决死胡同，其中1是墙，0是自由路径，3是结束，开始是
maze[1][1]maze = (
[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,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
[1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
[1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
[1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
[1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
[1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
[1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
[1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
)
现在是一个我的程序无法解决的迷宫我想这个迷宫的问题是它有一个“L”形或类似于之字形的死胡同，但老实说，我不知道发生了什么。例如，
maze[5][5]中的死胡同（我的程序被卡住了）在显示代码之前，我想解释一些关于它的主题：
我打印的所有字符串都是英语和葡萄牙语，语言之间用“/”隔开，所以不用担心。
为了探索迷宫，程序使用递归策略，并用两条探索的路径标记。
程序基于数组处理x和y坐标。x+1向下，x-1向上，y+1向右，y-1向左。
如果它陷入了一个死胡同，策略就是观察周围的情况，以发现它是哪种死胡同，然后返回，直到找到一条标记为0的新路径。
这些都是死胡同，你会在我的代码中看到。
如果可能的话，我想要一些关于如何改进我的代码或使其干净的提示。
所以，我们来：
maze = (
[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,1,1,1],
[1,0,1,1,1,0,1,1,1,1,1,1,0,1,1],
[1,0,1,0,0,0,0,0,0,1,1,1,0,1,1],
[1,0,0,0,1,1,1,1,0,0,0,1,0,0,1],
[1,1,0,1,1,0,0,1,1,1,0,1,1,0,1],
[1,1,0,1,1,1,0,0,0,1,0,1,0,0,1],
[1,0,0,1,1,1,1,1,0,1,0,1,1,0,1],
[1,0,1,1,0,0,0,0,0,1,0,0,0,0,1],
[1,0,0,0,0,1,1,1,1,1,0,1,1,1,1],
[1,1,1,1,1,1,1,1,1,1,3,1,1,1,1]
)
def solve(x, y):
if maze[x][y] == 0 or maze[x][y] == 2:
# To walk around and explore the maze
print('Visiting/Visitando xy({},{})'.format(x, y))
maze[x][y] = 2
if x < (len(maze) - 1) and (maze[x + 1][y] == 0 or maze[x + 1][y] == 3):
solve(x + 1, y)
elif y < (len(maze) - 1) and (maze[x][y + 1] == 0 or maze[x][y + 1] == 3):
solve(x, y + 1)
elif x > 0 and (maze[x - 1][y] == 0 or maze[x][y + 1] == 3):
solve(x - 1, y)
elif y > 0 and (maze[x][y - 1] == 0 or maze[x][y + 1] == 3):
solve(x, y - 1)
else:
# If it gets stuck in a dead end
step_back = 1
dead_end = True
# each possible kind of dead ends and the strategy to go back
if (maze[x + 1][y] == 1 or maze[x + 1][y] == 2) and maze[x][y - 1] == 1 and \
maze[x][y + 1] == 1 and maze[x - 1][y] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x - step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
solve(x - step_back, y - 1)
elif maze[x - step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
solve(x - step_back, y + 1)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x - step_back, y)
elif (maze[x - 1][y] == 1 or maze[x - 1][y] == 2) and maze[x][y - 1] == 1 and \
maze[x][y + 1] == 1 and maze[x + 1][y] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x + step_back][y - 1] == 0 or maze[x - step_back][y - 1] == 3:
solve(x + step_back, y - 1)
elif maze[x + step_back][y + 1] == 0 or maze[x - step_back][y + 1] == 3:
solve(x + step_back, y + 1)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x + step_back, y)
elif (maze[x][y + 1] == 1 or maze[x][y + 1] == 2) and maze[x + 1][y] == 1 and \
maze[x - 1][y] == 1 and maze[x][y - 1] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
solve(x - step_back, y)
elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
solve(x + step_back, y)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x, y + step_back)
elif (maze[x][y - 1] == 1 or maze[x][y - 1] == 2) and maze[x + 1][y] == 1 and \
maze[x - 1][y] == 1 and maze[x][y + 1] == 2:
print('Dead end in/Caminho sem saída encontrado em xy({},{})'.format(x, y))
while dead_end is True:
if maze[x][y - step_back] == 0 or maze[x][y - step_back] == 3:
solve(x - step_back, y)
elif maze[x][y + step_back] == 0 or maze[x][y + step_back] == 3:
solve(x + step_back, y)
else:
print("Going back/Voltando")
dead_end = False
step_back += 1
solve(x, y - step_back)
# to check if the end of the maze were found
if maze[x + 1][y] == 3 or maze[x - 1][y] == 3 or maze[x][y + 1] == 3 or maze[x][y - 1] == 3:
print('Exit found in/Saída encontrada em xy({},{})'.format(x, y))
solve(1,1)
最佳答案
一个简单的bfs/dfs就足以解决这个问题。从初始位置开始，跟踪所有已覆盖的节点。如果到达任何死区或重复任何位置，可以终止此路径。如果达到最终状态，则输出当前路径。
您可以找到有关此算法的更多信息。
关于python - 试图创建一个解决迷宫的程序，但是它陷入了特定的路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55834918/