迷宫求解数据结构设计完整代码

迷宫求解是一个经典的计算机科学问题，通常使用深度优先搜索（Depth-First Search, DFS）或广度优先搜索（Breadth-First Search, BFS）来解决。在设计数据结构时，我们通常会用到队列（用于BFS）或堆栈（用于DFS）以及一个二维数组来表示迷宫。

**1. 定义迷宫数据结构：**
我们可以定义一个二维数组`maze`，其中`maze[i][j]`表示某个位置是否是墙（0表示可以通过，1表示墙壁）。

class Maze:
    def __init__(self, maze):
        self.maze = maze
        self.rows = len(maze)
        self.cols = len(maze)

**2. 遍历方法：**
可以定义两个方法，一个用于BFS，一个用于DFS。

**BFS（广度优先搜索）:**

def bfs(sx, sy):
    visited = [[False] * self.cols for _ in range(self.rows)]
    queue = [(sx, sy)]
    visited[sx][sy] = True
    while queue:
        x, y = queue.pop(0)
        print(f"Visiting ({x}, {y})")
        # 检查周围是否有未访问的空格
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # 上下左右
            nx, ny = x + dx, y + dy
            if 0 <= nx < self.rows and 0 <= ny < self.cols and not visited[nx][ny] and maze[nx][ny] == 0:
                visited[nx][ny] = True
                queue.append((nx, ny))

**DFS（深度优先搜索）:**

def dfs(sx, sy, path=[]):
    path = path + [sx, sy]
    print(f"Dfs Path: {path}")
    if sx == self.rows - 1 and sy == self.cols - 1: # 到达终点
        return path
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # 上下左右
        nx, ny = sx + dx, sy + dy
        if 0 <= nx < self.rows and 0 <= ny < self.cols and not self.maze[nx][ny]:
            if dfs(nx, ny, path): # 递归回溯
                return path
    return None

**3. 使用示例：**

maze = [
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [1, 1, 0, 0],
    [0, 0, 0, 0]
]

start = (0, 0) # 起点
# 选择搜索算法（bfs或dfs）
# bfs(start, start)
dfs(start[0], start)