在python中使用递归解决迷宫
所以，我有一个作业，要求我用递归解一个迷宫。我会把作业指导贴出来，这样你就能明白我在说什么了。教授没怎么解释递归，他给了我们一些递归的例子，我会发布这些例子，但我希望有人能给我一个更深入的递归解释，以及我如何将其应用于解决迷宫。我不是要求任何人编写代码，我只是希望一些解释能让我走上正确的道路。感谢所有回答的人。
以下是我的例子：
def foo():
print("Before")
bar()
print("After")
def bar():
print("During")
def factorial(n):
"""n!"""
product = 1
for i in range(n,0,-1):
product *= i
return product
def recFac(n):
"""n! = n * (n-1)!"""
if(n == 1):
return 1
return n * recFac(n-1)
def hello():
"""Stack overflow!"""
hello()
def fib(n):
"""f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1"""
if n == 0 or n == 1: #base case
return n
return fib(n-1) + fib(n-2) #recursive case
def mult(a,b):
"""a*b = a + a + a + a ..."""
#base case
if (b == 1):
return a
#recursive case
prod = mult(a,b-1)
prod *= a
return prod
def exp(a,b):
"""a ** b = a* a * a * a * a *.... 'b times'"""
#base case
if (b==0):
return 1
if (b == 1):
return a
#recursive case
return exp(a,b-1)*a
def pallindrome(word):
"""Returns True if word is a pallindrome, False otherwise"""
#base case
if word == "" or len(word)==1:
return True
#recursive case
if word[0] == word[len(word)-1]:
word = word[1:len(word)-1]
return pallindrome(word)
else:
return False
以下是指南：
你要创建一个迷宫爬虫能够解决任何迷宫你给它递归的力量！
问题1-加载迷宫
在你解迷宫之前，你必须先加载它。对于本作业，你将使用迷宫的简单文本格式。您可以使用此示例迷宫或创建自己的迷宫。
这个问题的目的是加载任何给定的迷宫文件，并将其读入二维列表。例如：loadMaze（“somemaze.maze”）应该加载somemaze。迷宫文件并创建如下列表。。。
[['#','#','#','#','#','#','#','#','#'],
['#','S','#',' ',' ',' ','#','E','#'],
['#',' ','#',' ','#',' ',' ',' ','#'],
['#',' ',' ',' ','#',' ','#',' ','#'],
['#', #','#','#','#','#','#','#','#']]
请注意，列表中已删除所有“\r”和“\n”字符。为了简化下一个问题，您可以将此列表设置为全局变量。
接下来编写一个函数，以更好的格式打印迷宫：
例如。，
####################################
#S# ## ######## # # # # #
# # # # # # #
# # ##### ## ###### # ####### # #
### # ## ## # # # #### #
# # # ####### # ### #E#
####################################
在继续之前，用不同的迷宫测试代码。
问题2-准备解决迷宫
在解决迷宫之前，您需要找到起点！在您的代码中添加一个名为findStart（）的函数，该函数将搜索迷宫（逐个字符）并返回“S”字符的x和y坐标。您可以假设迷宫中最多存在一个这样的字符。如果在迷宫中没有找到“S”，则返回-1作为x和y坐标。
在继续之前，在多个位置（包括无位置）使用“S”测试代码。
问题3——解决迷宫！
最后，您已经准备好递归求解迷宫了！您的解决方案应该只需要一种方法：求解（y， x）
solve方法的一个实例应该可以解决迷宫中的一个位置。参数y和x是要求解的当前坐标。有几件事你的解决方法应该完成。它应该检查当前是否正在解决“E”的位置。在这种情况下，您的求解方法已成功完成。否则，它应该尝试递归地求解右边的空间。注意，您的方法应该只尝试求解空间，而不是墙（“#”）。如果这种递归没有到达终点，那么尝试向下、向左和向上。如果所有这些都失败了，代码应该回溯一个步骤，并尝试另一个方向。
最后，在解决迷宫时，您的代码应该留下其进度的指示器。如果它正在向右搜索，当前位置应该有一个'
一旦你的迷宫被解开，再次打印出迷宫。你应该看看走迷宫的分步指南。例如，
main("somemaze.maze")
#########
#S# #E#
# # # #
# # # #
#########
S位于（1,1）
#########
#S#>>v#E#
#v#^#>>^#
#>>^# # #
#########
使用不同的开始和结束位置测试代码，并且可以选择在各种迷宫中进行测试。
这是到目前为止我掌握的代码：但代码实际上并没有在迷宫中打印轨迹，我也不知道为什么。
def loadMaze():
readIt = open('Maze.txt', 'r')
readLines = readIt.readlines()
global mazeList
mazeList = [list(i.strip()) for i in readLines]
def showMaze():
for i in mazeList:
mazeprint = ''
for j in i:
mazeprint = mazeprint + j
print(mazeprint)
print('\n')
def solve(x,y, mazeList):
mazeList[x][y] = "o"
#Base case
if y > len(mazeList) or x > len(mazeList[y]):
return False
if mazeList[y][x] == "E":
return True
if mazeList[y][x] != " ":
return False
#marking
if solve(x+1,y) == True: #right
mazeList[x][y]= '>'
elif solve(x,y+1) == True: #down
mazeList[x][y]= 'v'
elif solve(x-1,y) == True: #left
mazeList[x][y]= '<'
elif solve(x,y-1) == True: #up
mazeList[x][y]= '^'
else:
mazeList[x][y]= ' '
return (mazeList[x][y]!= ' ')
共有3个答案
import os
class Maze_Crawler:
def __init__(self):
self.maze = []
def load_maze(self, path):
rows = []
with open(path, 'r') as f:
rows = f.readlines()
for i in range(len(rows)):
self.maze.append([])
for j in range(len(rows[i])-1):
self.maze[i].append(rows[i][j])
return self.maze
def get_start_coor(self):
for i in range(len(self.maze)):
for j in range(len(self.maze[i])):
if self.maze[i][j] == 'S':
return i, j
return -1, -1
def solve_maze(self, coor):
x, y = coor
if self.maze[x][y] == '#' or self.maze[x][y] == 'X':
return False
if self.maze[x][y] == 'E':
return True
if self.maze[x][y] != 'S':
self.maze[x][y] = 'X'
if self.solve_maze((x+1, y)):
if self.maze[x][y] != 'S':
self.maze[x][y] = 'v'
elif self.solve_maze((x-1, y)):
if self.maze[x][y] != 'S':
self.maze[x][y] = '^'
elif self.solve_maze((x, y+1)):
if self.maze[x][y] != 'S':
self.maze[x][y] = '>'
elif self.solve_maze((x, y-1)):
if self.maze[x][y] != 'S':
self.maze[x][y] = '<'
else:
return False
return True
def show_solution(self):
for i in range(len(self.maze)):
r = ''
for j in range(len(self.maze[i])):
if self.maze[i][j] == 'X':
r += ' '
else:
r += self.maze[i][j]
print(r)
以下是我对CodeEval的Labirynth挑战的解决方案：
import sys
sys.setrecursionlimit(5000)
class Maze(object):
FLOOR = ' '
WALLS = '*'
PATH = '+'
def __init__(self):
self.cols = 0
self.rows = 0
self.maze = []
def walk_forward(self, current_k, r, c):
self.maze[r][c] = current_k
next_k = current_k + 1
# up
if r > 1:
up = self.maze[r - 1][c]
if up != self.WALLS:
if up == self.FLOOR or int(up) > current_k:
self.walk_forward(next_k, r - 1, c)
# down
if r < self.rows - 1:
down = self.maze[r + 1][c]
if down != self.WALLS:
if down == self.FLOOR or int(down) > current_k:
self.walk_forward(next_k, r + 1, c)
# left
if c > 1:
left = self.maze[r][c - 1]
if left != self.WALLS:
if left == self.FLOOR or int(left) > current_k:
self.walk_forward(next_k, r, c - 1)
# right
if c < self.cols - 1:
right = self.maze[r][c + 1]
if right != self.WALLS:
if right == self.FLOOR or int(right) > current_k:
self.walk_forward(next_k, r, c + 1)
def walk_backward(self, r, c):
current_k = self.maze[r][c]
if not isinstance(current_k, int):
return False
self.maze[r][c] = self.PATH
up = self.maze[r - 1][c] if r > 0 else None
down = self.maze[r + 1][c] if r < self.rows - 1 else None
left = self.maze[r][c - 1] if c > 1 else None
right = self.maze[r][c + 1] if c < self.cols else None
passed = False
if up and isinstance(up, int) and up == current_k - 1:
self.walk_backward(r - 1, c)
passed = True
if down and isinstance(down, int) and down == current_k - 1:
self.walk_backward(r + 1, c)
passed = True
if left and isinstance(left, int) and left == current_k - 1:
self.walk_backward(r, c - 1)
passed = True
if right and isinstance(right, int) and right == current_k - 1:
self.walk_backward(r, c + 1)
def cleanup(self, cleanup_path=False):
for r in range(0, self.rows):
for c in range(0, self.cols):
if isinstance(self.maze[r][c], int):
self.maze[r][c] = self.FLOOR
if cleanup_path and self.maze[r][c] == self.PATH:
self.maze[r][c] = self.FLOOR
def solve(self, start='up', show_path=True):
# finding start and finish points
upper = lower = None
for c in range(0, self.cols):
if self.maze[0][c] == self.FLOOR:
upper = (0, c)
break
for c in range(0, self.cols):
if self.maze[self.rows - 1][c] == self.FLOOR:
lower = (self.rows - 1, c)
break
if start == 'up':
start = upper
finish = lower
else:
start = lower
finish = upper
self.cleanup(cleanup_path=True)
self.walk_forward(1, start[0], start[1])
length = self.maze[finish[0]][finish[1]]
if not isinstance(length, int):
length = 0
if show_path:
self.walk_backward(finish[0], finish[1])
self.cleanup(cleanup_path=False)
else:
self.cleanup(cleanup_path=True)
return length
def save_to_file(self, filename):
with open(filename, 'w') as f:
f.writelines(str(self))
def load_from_file(self, filename):
self.maze = []
with open(filename, 'r') as f:
lines = f.readlines()
for line in lines:
row = []
for c in line.strip():
row.append(c)
self.maze.append(row)
self.rows = len(self.maze)
self.cols = len(self.maze[0]) if self.rows > 0 else 0
def get_maze(self):
return copy.copy(self.maze)
def __str__(self):
as_string = u''
for row in self.maze:
as_string += u''.join([str(s)[-1] for s in row]) + "\n"
return as_string
maze = Maze()
maze.load_from_file(sys.argv[1])
maze.solve(show_path=True)
print str(maze)
（和我自己约会时，我实际上在高中的COBOL中遇到过这个问题。）
你可以把解决迷宫看作是采取步骤。
当你迈出一步时，每次都适用相同的规则。因为每次都适用相同的规则，所以你可以为每一步使用完全相同的指令集。当你迈出一步时，你只需再次调用相同的例程，更改参数以指示新步骤。这就是递归。你通过一步一步地解决问题来分解问题。
注意：一些递归解决方案将问题分成两半，每一半独立于另一半，当两个解决方案实际上是独立的时才起作用。它在这里不起作用，因为每一步（解决方案）都取决于前面的步骤。
如果你遇到了死胡同，你就会从死胡同里退出来，直到你找到一个仍然有可行方块需要检查的步骤。
有用的提示：你没有在通往出口的路上标记正确的路径，因为你不知道你现在走的一步是通往出口的路径的一部分。当你知道每一步确实是路径的一部分时，你在回来的路上标记路径。你可以这样做，因为每一步都记得它在迈出下一步之前在哪个方块。
相反，你在你尝试过的每一个方块上都做了一个标记，上面只写着：我来过这里，不需要再次检查这个方块。在打印溶液之前先把它们清理干净。
-
我正在尝试创建一个可以通过递归解决迷宫的程序。我的代码基于可以在网上找到的几个步骤，特别是： if（x， y在迷宫外）返回false if（x， y是目标）返回true if（x， y not open）返回false 将x， y标记为解路径的一部分 if（FIND-PATH（x， y的北方）==true）返回true if（FIND-PATH（East of x， y）==true）返回true
-
我得到了一些构建迷宫的代码，以及任何其他需要的东西，抽象迷宫类包含一个抽象方法“makeMove（int row，int col）”。这是我试图编写的解决迷宫的方法，向左、向右、向上、向下移动。 我刚刚开始做这件事，下面是我到目前为止的全部资料。 好的，我让代码运行到不再出现错误的地方。 感谢所有的帮助。
-
我正在尝试寻找到EndPotion的路径。这是一个递归函数。请帮助，我要自杀了。 这是给定的地图 我想递归地使用GetPath来到达上面地图中的EndPotion。参数是当前位置、结束位置和地图。对于这个例子，起始位置是（0,0）和结束，EndPotionis是（0,3），右上角。0代表墙壁，1代表路径。 我需要返回一个包含有效点的arraylist到结束位置。虽然我的数组大小始终为0，并且基本大
-
嗨~我被这个问题困住了。有人请帮帮我！！！！ 问题是程序会要求用户输入一个4到20之间的数字来决定迷宫的大小。它稍后会要求用户逐行输入迷宫的内容并将其存储到2D bool数组中（true表示阻塞，false表示清除）。然后程序从左上角开始，并尝试找到一条通往右下角的路径（可以向右、向左、向上、向下移动）。此时，程序还应该维护另一个char数组，该数组记录找到的路径（如果有的话）并在处理结束时打印出
-
我的任务是用回溯和递归的方法解决一个迷宫。这更多的是一个关于这个概念的概念问题。 回溯电话是如何接通的？从我所看到的所有示例来看，似乎递归总是在回溯步骤之前立即调用，所以回溯是无法实现的。谁能给我解释一下回溯步骤是怎么达到的？
-
我的作业是确定迷宫是否可以解决不使用Queue。如果是，请打印路径。我可以让Queue到达末尾，但它说它是无法解决的。实际上是。如果我将Final check if语句更改为： 然后它说它是可解的，但是当我尝试另一个不可解的迷宫时，它说它是可解的。不确定自己哪里错了。 我有一个单独的 Point 类，用于定义 Point 以及右、左、上方和下方的位置。我必须使用点（0，0）来标记开始，并使用点（行