迷宫求解数据结构代码

对于迷宫的求解，常用的数据结构是图（Graph）和栈（Stack）。下面是一个使用深度优先搜索（DFS）算法来解决迷宫问题的示例代码：

class MazeSolver:
    def __init__(self, maze):
        self.maze = maze
        self.rows = len(maze)
        self.cols = len(maze[0])
        self.visited = [[False] * self.cols for _ in range(self.rows)]
        self.solution = []

    def solve_maze(self, start_row, start_col):
        if not self._is_valid_position(start_row, start_col):
            return False

        if self._is_goal_position(start_row, start_col):
            self.solution.append((start_row, start_col))
            return True

        self.visited[start_row][start_col] = True
        self.solution.append((start_row, start_col))

        # 递归地探索四个方向
        if (self.solve_maze(start_row + 1, start_col) or
                self.solve_maze(start_row - 1, start_col) or
                self.solve_maze(start_row, start_col + 1) or
                self.solve_maze(start_row, start_col - 1)):
            return True

        # 回溯，将当前位置从解路径中移除
        self.solution.pop()
        return False

    def _is_valid_position(self, row, col):
        return 0 <= row < self.rows and 0 <= col < self.cols and not self.visited[row][col] and self.maze[row][col] == 0

    def _is_goal_position(self, row, col):
        return row == self.rows - 1 and col == self.cols - 1


# 示例用法
maze = [
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1],
    [0, 0, 0, 0, 0]
]

solver = MazeSolver(maze)
solver.solve_maze(0, 0)
print(solver.solution)

上述代码使用深度优先搜索算法（DFS）进行迷宫求解。其中，`maze`是一个二维列表，表示迷宫的布局，`0`表示可通过的路径，`1`表示墙壁。`solve_maze`方法接受起始位置的行和列作为参数，并返回布尔值表示是否找到了解路径。`solution`属性存储找到的解路径。