贪吃蛇算法与矩阵遍历：数据结构实践解析
1. 项目背景与核心思路
这个数据结构实验项目巧妙地将线性表与经典游戏贪吃蛇结合起来，通过矩阵遍历模拟蛇的移动路径。我在大学数据结构课程中第一次接触这个实验时，就被它精妙的设计所吸引——用基础的二维数组就能完整呈现贪吃蛇的核心逻辑。
实验要求实现一个n阶方阵的蛇形遍历：从左上角(0,0)出发，按照右→下→左→上的优先级转向，依次输出经过的元素。这本质上是在考察线性表的顺序存储和边界判断能力。比如4阶矩阵的输出序列应该是：0 1 2 3 7 11 15 14 13 12 8 4 5 6 10 9
关键点：转向判定条件包含两种情形——碰壁（坐标越界）或路径重复（元素已被访问）。这正好对应贪吃蛇游戏中的撞墙和咬到自己身体的场景。
2. 数据结构设计与实现
2.1 双矩阵存储结构
原始代码使用了两个n×n的二维数组：
int g[n][n]; // 存储矩阵原始数据 int A[n][n]; // 标记访问状态（-1表示未访问）这种设计虽然直观，但存在优化空间。实际只需要一个矩阵配合访问标记即可：
vector<vector<int>> matrix(n, vector<int>(n)); vector<vector<bool>> visited(n, vector<bool>(n, false));2.2 方向向量法
转向控制采用了经典的方位向量法：
int dx[] = {-1, 0, 1, 0}; // 上、右、下、左的x偏移 int dy[] = {0, 1, 0, -1}; // 对应的y偏移 int d = 1; // 初始方向向右这种表示法比直接写if-else更优雅，也更容易扩展。当需要转向时，只需执行：
d = (d + 1) % 4; // 顺时针转向3. 算法优化与边界处理
3.1 访问判定逻辑
原始代码的边界判断可以简化为：
if(a < 0 || a >= n || b < 0 || b >= n || visited[a][b]) { d = (d + 1) % 4; // 重新计算新方向坐标 }这里有个易错点：转向后需要立即重新计算坐标，否则会使用无效的(a,b)值。
3.2 循环终止条件
遍历次数必须严格等于n²：
for(int i = 0; i < n*n; i++) { // 每次循环处理一个元素 if(++count == n*n) break; // 保险措施 }4. 完整实现代码（C++11标准）
#include <iostream> #include <vector> using namespace std; void snakeTraversal(int n) { vector<vector<int>> matrix(n, vector<int>(n)); vector<vector<bool>> visited(n, vector<bool>(n, false)); // 初始化矩阵 for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) matrix[i][j] = i * n + j; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; int x = 0, y = 0, d = 1; for(int i = 0; i < n*n; ++i) { cout << matrix[x][y] << " "; visited[x][y] = true; int nx = x + dx[d]; int ny = y + dy[d]; if(nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) { d = (d + 1) % 4; nx = x + dx[d]; ny = y + dy[d]; } x = nx; y = ny; } } int main() { int n; cin >> n; snakeTraversal(n); return 0; }5. 常见问题与调试技巧
5.1 数组越界问题
当n较大时（如n>1000），在栈上声明大数组会导致栈溢出：
int g[n][n]; // 危险！n较大时崩溃解决方案：
- 使用动态分配（new/delete）
- 改用vector容器（推荐）
5.2 转向逻辑错误
常见错误是转向后忘记更新坐标：
// 错误示例 if(越界) { d = (d+1)%4; // 缺少坐标更新！ } x += dx[d]; // 使用了旧的(a,b)5.3 输出格式问题
实验要求行尾保留空格，但某些OJ平台会因此判错。保险做法：
for(int i = 0; i < n*n; ++i) { cout << matrix[x][y]; if(i < n*n - 1) cout << " "; // ...更新坐标... }6. 算法扩展思考
这个基础版本可以延伸出多个变种：
- 逆时针转向：调整方向向量顺序为左、上、右、下
- 螺旋矩阵：改变转向触发条件
- 多蛇竞争：扩展为多个"蛇"交替移动
- 图形化界面：用EasyX等库实现可视化
我在课程设计中曾实现过可视化版本，添加了这些特性：
- 蛇身增长效果（用链表存储身体坐标）
- 障碍物生成（修改访问判断条件）
- 速度分级（通过Sleep控制移动间隔）
经验之谈：在实现图形化时，建议将核心算法与界面逻辑分离。可以先完成控制台版本，再逐步添加图形模块。这样调试时可以通过打印日志快速定位问题。
