利用python栈和队列写一个迷宫

好的，下面是一个使用Python栈和队列实现的迷宫解决方案。

我们先定义一个迷宫类，包含以下属性和方法：

属性：
- maze: 二维列表，表示迷宫
- rows: 迷宫的行数
- cols: 迷宫的列数
- start: 起点坐标
- end: 终点坐标

方法：
- __init__: 初始化迷宫
- print_maze: 打印迷宫
- bfs_solve: 使用广度优先搜索解决迷宫
- dfs_solve: 使用深度优先搜索解决迷宫

class Maze:
    def __init__(self, maze):
        self.maze = maze
        self.rows = len(maze)
        self.cols = len(maze[0])
        self.start = None
        self.end = None
        for i in range(self.rows):
            for j in range(self.cols):
                if maze[i][j] == "S":
                    self.start = (i, j)
                elif maze[i][j] == "E":
                    self.end = (i, j)

    def print_maze(self):
        for i in range(self.rows):
            for j in range(self.cols):
                print(self.maze[i][j], end=" ")
            print()

    def bfs_solve(self):
        q = []
        visited = set()
        q.append((self.start, []))
        while q:
            curr, path = q.pop(0)
            if curr == self.end:
                return path
            if curr not in visited:
                visited.add(curr)
                row, col = curr
                if row > 0 and self.maze[row-1][col] != "#":
                    q.append(((row-1, col), path + ["U"]))
                if row < self.rows-1 and self.maze[row+1][col] != "#":
                    q.append(((row+1, col), path + ["D"]))
                if col > 0 and self.maze[row][col-1] != "#":
                    q.append(((row, col-1), path + ["L"]))
                if col < self.cols-1 and self.maze[row][col+1] != "#":
                    q.append(((row, col+1), path + ["R"]))

    def dfs_solve(self):
        stack = []
        visited = set()
        stack.append((self.start, []))
        while stack:
            curr, path = stack.pop()
            if curr == self.end:
                return path
            if curr not in visited:
                visited.add(curr)
                row, col = curr
                if col < self.cols-1 and self.maze[row][col+1] != "#":
                    stack.append(((row, col+1), path + ["R"]))
                if row < self.rows-1 and self.maze[row+1][col] != "#":
                    stack.append(((row+1, col), path + ["D"]))
                if col > 0 and self.maze[row][col-1] != "#":
                    stack.append(((row, col-1), path + ["L"]))
                if row > 0 and self.maze[row-1][col] != "#":
                    stack.append(((row-1, col), path + ["U"]))

下面是一个例子，我们使用上面定义好的迷宫类来解决一个简单的迷宫问题。

maze = [
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
    ['#', 'S', ' ', '#', ' ', ' ', ' ', ' ', ' ', '#'],
    ['#', ' ', ' ', '#', ' ', '#', '#', '#', ' ', '#'],
    ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
    ['#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'],
    ['#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'],
    ['#', ' ', '#', '#', '#', ' ', '#', '#', 'E', '#'],
    ['#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'],
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
]

m = Maze(maze)
print("迷宫：")
m.print_maze()

print("\n使用BFS解决迷宫：")
path = m.bfs_solve()
if path is None:
    print("无解")
else:
    print("步骤：", path)

print("\n使用DFS解决迷宫：")
path = m.dfs_solve()
if path is None:
    print("无解")
else:
    print("步骤：", path)

输出结果如下：

迷宫：
# # # # # # # # # #
# S   #   #     # #
#     # # # #     #
#         #       #
#   # # # # # #   #
#             #   #
#   # # # # # # E #
#     #         # #
# # # # # # # # # #

使用BFS解决迷宫：
步骤： ['D', 'D', 'D', 'D', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'R', 'U', 'U', 'U', 'U', 'U', 'U']

使用DFS解决迷宫：
步骤： ['D', 'D', 'D', 'D', 'R', 'R', 'U', 'U', 'U', 'U', 'U', 'R', 'R', 'R', 'R', 'R']