以下是实现迷宫生成和求解的完整代码，包含所需的各个类和函数： ```python # 定义单元格类 class Cell: def __init__(self, row, col): self.row = row self.col = col self.N = True self.W = True self.S = True self.E = True self.visited = False def coordinate(self): return (self.row, self.col) def breakWall(self, direction): if direction == 'N': self.N = False elif direction == 'W': self.W = False elif direction == 'S': self.S = False elif direction == 'E': self.E = False # 绘制迷宫函数 def draw_maze(maze, width, height): for i in range(height): # 绘制顶部墙体 for j in range(width): print('+', end='') if maze[i][j].N: print('--', end='') else: print(' ', end='') print('+') # 绘制左侧墙体和内部通道 for j in range(width): if maze[i][j].W: print('|', end='') else: print(' ', end='') print(' ', end='') print('|') # 绘制底部墙体 print('+', end='') for j in range(width): print('--', end='') print('+') # 自定义栈类 class Stack: def __init__(self): self.items = [] def is_empty(self): return len(self.items) == 0 def push(self, item): self.items.append(item) def pop(self): if not self.is_empty(): return self.items.pop() return None def peek(self): if not self.is_empty(): return self.items[-1] return None # 迷宫生成函数 def maze_generation(width, height): # 创建单元格网格 maze = [[Cell(i, j) for j in range(width)] for i in range(height)] stack = Stack() start_cell = maze[0][0] start_cell.visited = True stack.push(start_cell) while not stack.is_empty() and stack.peek() != maze[height - 1][width - 1]: current_cell = stack.peek() neighbors = [] row, col = current_cell.row, current_cell.col # 检查上方单元格 if row > 0 and not maze[row - 1][col].visited: neighbors.append((maze[row - 1][col], 'N')) # 检查右侧单元格 if col < width - 1 and not maze[row][col + 1].visited: neighbors.append((maze[row][col + 1], 'E')) # 检查下方单元格 if row < height - 1 and not maze[row + 1][col].visited: neighbors.append((maze[row + 1][col], 'S')) # 检查左侧单元格 if col > 0 and not maze[row][col - 1].visited: neighbors.append((maze[row][col - 1], 'W')) if neighbors: next_cell, direction = random.choice(neighbors) if direction == 'N': current_cell.breakWall('N') next_cell.breakWall('S') elif direction == 'E': current_cell.breakWall('E') next_cell.breakWall('W') elif direction == 'S': current_cell.breakWall('S') next_cell.breakWall('N') elif direction == 'W': current_cell.breakWall('W') next_cell.breakWall('E') next_cell.visited = True stack.push(next_cell) else: stack.pop() return maze # 链表节点类 class Node: def __init__(self, cell): self.cell = cell self.E = None self.S = None self.W = None self.N = None # 链表类 class LinkedList: def __init__(self): self.head = None def __str__(self): result = "" current = self.head while current: if result: if current.cell.row > prev.cell.row: result += "+-S-+" elif current.cell.row < prev.cell.row: result += "+-N-+" elif current.cell.col > prev.cell.col: result += "+-E-+" elif current.cell.col < prev.cell.col: result += "+-W-+" result += str(current.cell.coordinate()) prev = current current = current.E or current.S or current.W or current.N return result def add(self, newNode): if not self.head: self.head = newNode else: current = self.head while current.E or current.S or current.W or current.N: if current.E: current = current.E elif current.S: current = current.S elif current.W: current = current.W elif current.N: current = current.N if newNode.cell.row > current.cell.row: current.S = newNode elif newNode.cell.row < current.cell.row: current.N = newNode elif newNode.cell.col > current.cell.col: current.E = newNode elif newNode.cell.col < current.cell.col: current.W = newNode def removeLastNode(self): if not self.head: return if not self.head.E and not self.head.S and not self.head.W and not self.head.N: self.head = None return current = self.head prev = None while current.E or current.S or current.W or current.N: prev = current if current.E: current = current.E elif current.S: current = current.S elif current.W: current = current.W elif current.N: current = current.N if prev.E == current: prev.E = None elif prev.S == current: prev.S = None elif prev.W == current: prev.W = None elif prev.N == current: prev.N = None # 迷宫求解函数 def maze_resolution(maze): start_cell = maze[0][0] end_cell = maze[len(maze) - 1][len(maze[0]) - 1] stack = Stack() stack.push(start_cell) path = LinkedList() visited = set() while not stack.is_empty(): current_cell = stack.pop() if current_cell == end_cell: path.add(Node(current_cell)) break if current_cell not in visited: visited.add(current_cell) path.add(Node(current_cell)) row, col = current_cell.row, current_cell.col if not current_cell.N and maze[row - 1][col] not in visited: stack.push(maze[row - 1][col]) if not current_cell.E and maze[row][col + 1] not in visited: stack.push(maze[row][col + 1]) if not current_cell.S and maze[row + 1][col] not in visited: stack.push(maze[row + 1][col]) if not current_cell.W and maze[row][col - 1] not in visited: stack.push(maze[row][col - 1]) else: path.removeLastNode() return path import random # 测试代码 width = 5 height = 5 maze = maze_generation(width, height) draw_maze(maze, width, height) solution = maze_resolution(maze) print("求解路径:", solution) ``` ### 代码解释 - **Cell类**：用于表示迷宫中的单元格，包含了单元格的坐标、四个方向的墙体信息以及是否被访问过的状态。`__init__`方法用于初始化单元格，`coordinate`方法返回单元格的坐标，`breakWall`方法用于拆除指定方向的墙体。 - **draw_maze函数**：根据迷宫的单元格信息，使用字符绘制出迷宫的图形。 - **Stack类**：自定义的栈类，用于在迷宫生成和求解过程中保存单元格。 - **maze_generation函数**：使用回溯法生成迷宫，从起始单元格开始，随机选择未访问的相邻单元格并打通它们之间的墙体，直到所有单元格都被访问过。 - **LinkedList类**：用于保存迷宫的求解路径，包含`__init__`、`__str__`、`add`和`removeLastNode`方法。 - **maze_resolution函数**：使用深度优先搜索算法找到从起点到终点的路径，遇到死胡同时进行回溯。 ###