Maze Solver

项目背景

数据结构课程设计需要解决一个实际问题来综合运用所学知识。选择迷宫问题的原因是它天然涉及多种核心数据结构：二维数组表示地图、栈实现 DFS 回溯、队列实现 BFS 层序遍历、优先队列实现 A* 搜索。

核心功能

• 迷宫生成：递归回溯法生成完美迷宫
• 多种寻路：DFS、BFS、A* 算法对比
• 可视化：Qt GUI 实时展示生成和寻路过程
• 交互控制：调整迷宫大小、选择算法、步进/自动播放
• 性能统计：步数、时间、空间复杂度对比

系统架构

graph LR
  A[User Input] --> B[Controller]
  B --> C[Maze Generator]
  B --> D[Path Finder]
  C --> E[Maze Data]
  D --> E
  E --> F[Qt View]
  F --> G[Animation]

算法对比

项目结构

data-structures-course-design/
├── coding/
│   └── MazeProject/      # Qt C++ 源码
├── python版本/            # Python 原型实现
├── report/               # 课程设计报告
├── README.md
└── *.png                 # 演示截图

核心代码

迷宫网格模型

Loading code...

寻路算法接口

Loading code...

效果展示

技术要点

迷宫生成算法

递归回溯法（Recursive Backtracking）：

1. 从起点开始，随机选择一个未访问的邻接单元格
2. 打通当前单元格与选中单元格之间的墙
3. 递归对新单元格重复上述过程
4. 若无未访问邻接单元格，回溯到上一个单元格

A* 启发函数

f(n) = g(n) + h(n)
g(n): 从起点到 n 的实际代价
h(n): 从 n 到终点的曼哈顿距离估计

Qt 自定义绘图

• QPainter 绘制网格、墙壁、路径
• QTimer 控制动画帧率
• 信号-槽机制解耦算法与 UI