python用栈求解迷宫问题

以下是使用栈求解迷宫问题的Python代码示例：

# 定义迷宫类
class Maze:
    def __init__(self, maze_array):
        self.maze_array = maze_array
        self.width = len(maze_array[0])
        self.height = len(maze_array)
        self.start = (0, 0)  # 起点坐标
        self.end = (self.width - 1, self.height - 1)  # 终点坐标

    # 判断当前位置是否为通路
    def is_path(self, pos):
        x, y = pos
        if x < 0 or x >= self.width or y < 0 or y >= self.height:
            return False
        return self.maze_array[y][x] == 0

    # 获取当前位置的四个相邻位置
    def get_neighbors(self, pos):
        x, y = pos
        neighbors = [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]
        return [n for n in neighbors if self.is_path(n)]

    # 使用栈求解迷宫问题
    def solve(self):
        stack = [self.start]
        visited = set()
        while stack:
            current = stack[-1]
            if current == self.end:
                return stack
            visited.add(current)
            neighbors = self.get_neighbors(current)
            unvisited_neighbors = [n for n in neighbors if n not in visited]
            if unvisited_neighbors:
                next_pos = unvisited_neighbors[0]
                stack.append(next_pos)
            else:
                stack.pop()
        return None

使用方法：

# 定义迷宫数组
maze_array = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
]

# 创建迷宫对象
maze = Maze(maze_array)

# 求解迷宫问题
path = maze.solve()

# 输出结果
if path:
    print("迷宫有解，路径为：", path)
else:
    print("迷宫无解")