Python 迷宫递归问题：不递归实现

Question

我在尝试递归解决迷宫，能够让它按照我想要的方向前进（检查是否可以通行，并将其标记为已经到达过），但是当它遇到死路时，它不会递归回去到其他开放的地方继续寻找。我使用递归的方式有什么问题吗？

class maze(object):
    def __init__(self, maze):
        self.maze = maze
        self.maze2d = []
        n = 0
        i = 0
        for row in self.maze:
            self.maze2d.append([])
            print(row)
            for col in row:
                self.maze2d[i].append(col)
            i += 1
        print(self.maze2d)

    def find_start(self):
        x = 0 
        y = 0
        for row in self.maze2d:
            for index in row:
                if index == "S":
                    self.maze2d[x][y] = index
                    return x,y
                y += 1
            x += 1
            y = 0
        return -1

    def mazeSolver(self,x,y,path):
        if self.maze2d[x][y] == "E":
            return True
        else:
            if self.maze2d[x] != 0: 
                if self.maze2d[x+1][y] == ".":
                    self.maze2d[x+1][y] = "_"
                    self.mazeSolver(x+1,y,path + "S")
            if self.maze2d[x] < len(self.maze2d):
                if self.maze2d[x-1][y] == ".":
                    self.maze2d[x-1][y] = "_"
                    self.mazeSolver(x-1,y,path + "N")
            if y < len(self.maze2d[x]): 
                if self.maze2d[x][y+1] == ".":
                    self.maze2d[x][y+1] = "_"
                    self.mazeSolver(x,y+1,path + "E")
            if self.maze2d[y] != 0:
                if self.maze2d[x][y-y] == ".":
                    self.maze2d[x][y-1] = "_"
                    self.mazeSolver(x,y-1,path + "W")

我正在调用函数和迷宫本身的位置：

from eachstep import *

maze1 = []

maze1.append("S..*..")
maze1.append("*...*.")
maze1.append("..*..E")

var1 = maze(maze1)
x,y = var1.find_start()
var1.mazeSolver(x,y,"")

- Jen

---

请澄清一下，字符 . 和 * 分别代表什么？ - Chris Laplante

@Jen 你在递归点忘记写 return 了吗？ - satoru

在搜索 x+1 或 x-1 之前，您应该验证自己不是在该行的末尾或开头。y 同理。 - Pablo Reyes

@PauloScardine - 为什么我需要这样做呢？我对递归的理解是，如果其中一个函数结束了，它会自动追溯到上一个函数。我的程序还没有达到999次调用的数量，所以你认为还需要改变吗？ - Jen

@Jen。在执行您的原始代码时，我遇到了错误：“”“IndexError：list index out of range”“”。这就是我不得不修改您检查是否位于行或列的开头或结尾的方式的原因。 - Pablo Reyes

Answer 1

我用这个函数替换了你的mazeSolver函数，并在最后打印了路径：

def mazeSolver(self,x,y,path):
    if self.maze2d[x][y] == '.':
        self.maze2d[x][y] = "_"
    if self.maze2d[x][y] == "E":
        print path
        return True
    else:
        if x < len(self.maze2d)-1: 
            if self.maze2d[x+1][y] in ['.','E']:
                self.mazeSolver(x+1,y,path + "S")
        if x > 0:
            if self.maze2d[x-1][y]  in ['.','E']:
                self.mazeSolver(x-1,y,path + "N")
        if y < len(var1.maze2d[x])-1: 
            if self.maze2d[x][y+1]  in ['.','E']:
                self.mazeSolver(x,y+1,path + "E")
        if y > 0:
            if self.maze2d[x][y-y]  in ['.','E']:
                self.mazeSolver(x,y-1,path + "W")

>>> var1.mazeSolver(x,y,"")
ESEESEE
>>>> var1.maze2d
[['S', '_', '_', '*', '.', '.'],
 ['*', '_', '_', '_', '*', '.'],
 ['_', '_', '*', '_', '_', 'E']]

- Pablo Reyes

Answer 2

你的代码永远不会结束，因为它只访问值为. 的位置，而终点的值为E。

- desired login