简介《武汉理工大学数据结构与算法实验——欢乐连连看非线性结构》是一份面向高校数据结构课程设计或算法综合实践的完整项目资源重点展示了二叉树、图、哈希表等非线性结构在连连看游戏中的落地应用适合计算机专业学生、课程实验参考者及算法入门开发者参考学习。压缩包为 7z 格式共 281 个文件整体约 226.97MB包含 Visual Studio 解决方案(.sln)、C 源文件(.cpp/.h)、编译生成的可执行文件(.exe)、位图素材(.bmp)以及 Git 版本控制记录等工程配置既有源码也有可直接运行的程序。项目实现涉及 DFS/BFS 路径搜索、最短路径计算、哈希表状态记录等典型算法有助于理解非线性结构如何解决实际匹配与消除问题。目前已有 2570 人学习/下载对于想通过趣味游戏项目巩固数据结构知识、查看完整工程结构的读者来说是一份具有参考价值的实践样本。1. 欢乐连连看从游戏规则看非线性数据结构的实际意义很多同学拿到“数据结构与算法实验——欢乐连连看”这个题目时第一反应是“这不就是个二维数组消消乐吗哪里用到非线性结构了”。如果你也这么想那这门实验课大概率要翻车。连连看的棋盘确实长着一张“线性表”的脸——一个board[row][col]二维数组就能存下所有方块但这只是表象。真正决定游戏体验的是方块与方块之间那条蜿蜒的“连接路径”这条路径的搜索与合法性判断依赖的是图论中的广度优先遍历思想而棋盘上有限连通区域的形成与坍塌又涉及连通分量与树的层级关系。换句话说你用数组存棋盘用图来思考连通用线性表做界面渲染三者缺一不可。该实验被冠以“非线性结构”之名核心考察点在于你能不能跳出for循环里一个个挨着比对的老套路把二维棋盘抽象成一个具有节点和边的逻辑图再在这个图上设计路径搜索策略。这也是本篇笔记存在的意义。我们把“欢乐连连看”拆成四层棋盘的数据映射、方块的匹配规则、两点之间拐点最少的路径搜索、以及路径搜索背后的 BFS/DFS 算法选型。四层全部打通你的实验报告才真正有“非线性结构”的内味否则评委老师一眼就能看出你在拿线性表的遍历硬凑图论的结论。适合读这篇笔记的读者有三类第一类是正在为实验报告发愁的在校生你需要一套能自圆其说的算法设计思路第二类是想要把课程设计做成“有点东西”的项目而不是交差就完事的同学这里附带性能优化与交互细节第三类是单纯对“连连看算法”感兴趣的编程爱好者这篇笔记能让你少走大半年的弯路。下面的内容我不会给你贴一大段所谓的“完整源码”而是把构成这个实验的每一个决策点、每一段关键代码、每一个让你挠头的边界条件拆开揉碎。2. 棋盘的数据映射用图而非数组来理解非线性关系2.1 二维数组的谎言为什么线性存储掩盖了节点间的真实联系初次接触连连看你会觉得这题简单到离谱。定义一个int board[ROW][COL]0 表示空格非 0 表示方块类型编号然后用两层for循环遍历整个棋盘判断两个方块类型是否相同。听起来完全符合线性表的操作范式但一旦你开始写“判断两个方块能否消除”的函数线性表思维就会立刻失效。因为连连看的消除条件不依赖于方块本身的属性而依赖于两个方块之间是否存在一条合法的路径且这条路径的拐点不得超过两个。什么是拐点从方块 A 到方块 B如果能够沿着同行或同列的水平/垂直线段移动路径中的方向发生改变的位置就是一个拐点。直连是 0 拐点经过一个中间转换点横线和竖线的交点是 1 拐点经过两个转换点是 2 拐点。这个判断逻辑跟数组索引的加减完全不在一个层面——它要求你把整个棋盘看作一个网络每个空格都是一个通路节点每个方块都是一个障碍节点两个节点之间能否通信取决于节点之间的连通性。而“连通性”这三个字恰恰是图论中最核心的概念也是线性表结构无法直接表达的东西。我的做法是在动手写任何算法之前先画一张棋盘抽象图。把二维坐标(row, col)映射为图中的节点 ID把相邻的空白格子视为一条无向边把有方块的格子从图中剔除。这样一来“A 到 B 能否连通”就变成了“图 G 中节点 A 到节点 B 是否存在一条路径”。为了让路径搜索具备可行性通常我们还会在棋盘外围补一层“虚拟空行”让原本贴着棋盘边界的方块也能通过外部通道相连。这个“外围扩展”的操作非常关键很多新手第一次写连连看发现最左上角和最右下角的方块明明能通过边缘路径相连程序却认为它们不通原因就是忘记给棋盘加一圈外框。下面这段代码展示了棋盘初始化与外围扩展的标准姿势。#define ROW 10 #define COL 10 #define EXTEND_ROW ROW 2 #define EXTEND_COL COL 2 int board[EXTEND_ROW][EXTEND_COL]; void init_board() { // 外圈全部置 0代表空白可通行区域 for (int i 0; i EXTEND_ROW; i) { board[i][0] 0; board[i][EXTEND_COL - 1] 0; } for (int j 0; j EXTEND_COL; j) { board[0][j] 0; board[EXTEND_ROW - 1][j] 0; } // 内部填充方块为 0 的位置表示已被消除 for (int i 1; i ROW; i) { for (int j 1; j COL; j) { // 模拟随机生成不同类型方块 board[i][j] rand() % 5 1; } } }这段代码的逻辑很容易理解我们用一个比实际棋盘大一圈的二维数组来存储游戏状态所有边界外的坐标统一置为 0当作可连通的空白区域。rand() % 5 1是临时方案实际项目中会确保每种类型的方块个数为偶数否则游戏后期必然出现无法消除的死局。参数层面EXTEND_ROW和EXTEND_COL的引入让所有路径搜索算法都不需要再做复杂的边界判断因为我们把“边界外”这个特殊状态变成了“空白格子”这个普通状态极大简化了后续代码编写。有人说这不还是在用二维数组吗哪来的非线性结构你需要换一个视角二维数组只是图的一种存储载体真正决定数据关系的是你如何在逻辑上解释这个数组。在线性表语义下board[i][j]只跟它的索引相关在图语义下board[i][j]跟它上下左右的邻居节点相关这些邻居关系构成了逻辑上的邻接链表。实验要求里写得清清楚楚你必须使用“非线性结构”这里的非线性结构指的不是你的存储介质而是你算法设计中对数据关系的组织方式——用图的思维去指挥数组的操作。2.2 连通分量的应用消除后棋盘会自动更新吗棋盘上的方块被消除后会留下一个空位。这个空位在逻辑上意味着一个障碍节点变成了通路节点。如果你在运行算法时重新遍历整张图来更新连通分量效率会非常低。实际操作中我们并不需要显式维护一个完整的连通分量表因为每次判断两块方块是否连通时我们只关心局部路径情况而不是全局连通性。但你是否想过当一大批方块被消除后图中某些原本被阻断的区域会突然连通这会不会影响后续的路径判断答案是不会影响正确性因为路径搜索是实时进行的。每次判断“A 与 B 是否可消”我们都会基于当前棋盘状态重新搜索路径。操作顺序上应该是“先判断路径再执行消除然后修改数组中对应位置的值”。修改数组的动作永远不会回溯到之前的搜索结果。这里有一个严重的认知误区有些同学试图维护一个“动态连通性数据结构”每次消除后都重新计算全盘连通分量这完全背离了连连看的规则。连连看的核心约束是“两点之间是否存在一条合法路径”不是“两个点是否属于同一个连通区域”。属于同一连通区域的两点之间必然存在路径但这条路径的拐点数量可能大于 2而连连看要求不能超过 2 个拐点所以全局连通分量信息对你的搜索条件没有任何帮助。这就是为什么我们不用并查集这类高级连通性结构而是老老实实做局部搜索。图示关系上请记住三条规则只有值为 0 的格子可以走路径最多只能拐两次路径不能穿过任何有方块或未消除的格子。这个映射关系一旦建立后面所有的代码都会朝着“简化路径搜索”的方向演进而不是朝着“优化连通性更新”的方向。这个决策决定了你的代码结构一个主控函数接收两个坐标调用内部三个不同层级的判断函数从易到难依次判定直连、一拐、两拐。下一个章节我们详细展开这三层判定函数的图论本质和代码实现。3. 路径搜索的层次递进零拐点、单拐点与双拐点的图论推演3.1 直线可达与单拐点路径从邻接节点到中间节点的枚举连连看的路径搜索可以拆成三个递进的层级每一层级都建立在前一层级的基础上。最基础的层级是直线可达。直线可达的判断逻辑最简单两个方块位于同一行或同一列且二者之间所有格子均为 0空白。写成代码就是遍历两者之间的所有坐标逐一检查board[i][j] 0。这段代码没有技术含量但它却是整个连连看算法正确性的基石——因为后续所有复杂的拐弯路径本质上都是由一段段的直线段拼接而成的。单拐点路径的判断开始变得有趣。所谓单拐点是指从 A 出发先沿水平或垂直方向走到达某个中间点后转向再沿垂直或水平方向到达 B。这个中间点有一个几何特征它的横坐标与 A 相同或纵坐标与 A 相同而纵坐标与 B 相同或横坐标与 B 相同。换言之如果 A 的坐标是(r1, c1)B 的坐标是(r2, c2)那么候选的中间点就两个(r1, c2)和(r2, c1)。你需要检查这两个中间点是否为空白以及 A 到中间点、中间点到 B 之间的两条线段是否都是直线可达。算法的图论本质是在图中枚举 A 的所有“同行邻居”和“同列邻居”看能否通过这些邻居中转连接到 B。这里的关键优化点在于你不用枚举 A 所有的邻居只需要枚举两个交点即可。但这两个交点必须满足“该交点本身是空白格子”。有些同学的代码里漏掉了对中间点是否空白进行检查结果出现方块穿过方块的神奇现象——两条路径明明被障碍物截断程序却判定连通。写代码时一定要把“线段上所有格子为 0 且中间点本身为 0”这一条件整合到同一个循环中避免分层判断带来的逻辑漏洞。看下面的实现。// 判断两个点之间的直线是否完全空 int is_line_empty(int r1, int c1, int r2, int c2) { // 同行 if (r1 r2) { int min_c c1 c2 ? c1 : c2; int max_c c1 c2 ? c1 : c2; for (int c min_c 1; c max_c; c) { if (board[r1][c] ! 0) return 0; // 有方块阻挡 } return 1; } // 同列 else if (c1 c2) { int min_r r1 r2 ? r1 : r2; int max_r r1 r2 ? r1 : r2; for (int r min_r 1; r max_r; r) { if (board[r][c1] ! 0) return 0; } return 1; } return 0; // 既不同行也不同列直接返回 false } // 判断单拐点路径 int is_one_turn(int r1, int c1, int r2, int c2) { int mid_r r1, mid_c c2; // 中间点必须为空白 if (board[mid_r][mid_c] 0) { if (is_line_empty(r1, c1, mid_r, mid_c) is_line_empty(mid_r, mid_c, r2, c2)) { return 1; } } mid_r r2; mid_c c1; if (board[mid_r][mid_c] 0) { if (is_line_empty(r1, c1, mid_r, mid_c) is_line_empty(mid_r, mid_c, r2, c2)) { return 1; } } return 0; }这段代码的参数定义非常朴素四个整型坐标值分别代表两个点的行和列。is_line_empty函数负责判断两个坐标是否在同一行或同一列且路径畅通它排除了首尾两个点本身只检查中间的格子。而is_one_turn函数则通过两个候选中间点去测试能否通过一次转弯连通。这里有一个我踩过的坑当你把 A 的坐标设为(r1, c1)、B 坐标设为(r2, c2)时候选点(r1, c2)和(r2, c1)如果和 A 或 B 重合怎么办比如 A 和 B 本就在同一行那(r1, c2)就是 B 自己(r2, c1)就是 A 自己。在这种边界下is_one_turn会错误地返回 1因为它沿着“零长度路径”连接。所以在调用is_one_turn之前你应该在主函数中先判断 A 和 B 是否同行或同列如果是直接走直线逻辑否则再进入拐点逻辑。这种分层管理的思路可以避免很多边界条件互相干扰。3.2 双拐点路径的 BFS 搜索把枚举问题转化为层次遍历问题双拐点路径的搜索是连连看的核心难点也是“非线性结构”实验报告的满分关键。双拐点的定义是路径中恰好存在两个转向点。从图论视角来看搜索双拐点路径等价于以下过程先让 A 沿着所有可能的方向走一条直线水平或垂直走到某个中间点 M1再从 M1 沿着与其垂直的方向走一条直线走到另一个中间点 M2最后从 M2 沿着与 M1 方向垂直的方向走一条直线到 B。这个过程可以看作是一个受限的广度优先搜索从 A 出发先探索所有直线可达的节点再从这些节点出发探索与之垂直方向上的直线可达节点看最终能否覆盖到 B。用枚举法实现双拐点搜索最朴素的方式是遍历所有空白格子作为潜在拐点判断 A 到中间点、中间点到 B 是否分别单拐可达。这种做法的复杂度为 O(N^2)对于 10x10 的棋盘尚可接受但如果你把棋盘扩展到 20x20 或带有更多空白区域性能会急剧下降。而 BFS 的方法则聪明得多第一轮 BFS 从 A 出发向四个方向延伸把从 A 出发直线可达的连续空白格子全部标记为“距离 1”第二轮 BFS 从这些已被标记为“距离 1”的格子出发但方向和第一轮的方向垂直因为你要制造拐点继续延伸并标记为“距离 2”如果在第二轮延伸过程中覆盖到了 B则说明双拐点路径存在。需要特别说明的是如果你用 DFS深度优先搜索来做路径搜索会存在路径搜索过深导致时间开销过大、甚至陷入死胡同的问题。连连看的路径搜索必须是“层次感”明确的搜索BFS 天然契合这个需求。很多同学在这个地方走了弯路想着用 DFS 递归地朝四个方向试探结果要么栈溢出要么搜索路径绕了很远才发现死路。这是因为 DFS 无法保证搜索路径的拐点数量最小化它可能找到一条拐了 10 次弯的路径而你根本无法判断它是否满足“不超过两个拐点”的约束。BFS 则不同BFS 天然具备“由近及远”的搜索特征第一轮搜索保证找到距离为 1 的可达节点第二轮搜索保证找到距离为 2 的可达节点天然匹配连连看的拐点约束。typedef struct { int row; int col; } Point; // BFS 层次遍历寻找两拐连接 int is_two_turn_bfs(int r1, int c1, int r2, int c2) { int dir[4][2] {{1,0}, {-1,0}, {0,1}, {0,-1}}; int visited[EXTEND_ROW][EXTEND_COL] {0}; Point queue[EXTEND_ROW * EXTEND_COL]; int head 0, tail 0; // 第一轮从 A 出发向四个方向直线延伸 for (int i 0; i 4; i) { int nr r1 dir[i][0]; int nc c1 dir[i][1]; while (board[nr][nc] 0 nr 0 nr EXTEND_ROW nc 0 nc EXTEND_COL) { if (!visited[nr][nc]) { visited[nr][nc] 1; queue[tail].row nr; queue[tail].col nc; tail; } nr dir[i][0]; nc dir[i][1]; } } // 第二轮从第一轮找到的所有点出发沿垂直方向延伸 while (head tail) { Point cur queue[head]; head; for (int i 0; i 4; i) { int nr cur.row dir[i][0]; int nc cur.col dir[i][1]; if (nr r2 nc c2) return 1; // 直接到达 B while (nr 0 nr EXTEND_ROW nc 0 nc EXTEND_COL board[nr][nc] 0) { if (nr r2 nc c2) return 1; if (!visited[nr][nc]) { visited[nr][nc] 1; queue[tail].row nr; queue[tail].col nc; tail; } nr dir[i][0]; nc dir[i][1]; } } } return 0; }这段代码有两个极其容易翻车的细节。细节一while (board[nr][nc] 0 ...)循环的边界条件必须先检查数组下标是否越界再检查board值。C 语言中如果数组下标越界你读到的可能恰好是 0这会导致程序错误地继续循环甚至访问到完全不相关的内存区域。细节二第二轮的“垂直方向”约束代码里我依旧遍历了全部 4 个方向这样搜索范围会扩大导致某些路径实际上拐了 4 个弯也能被误判为两拐。所以你必须给第二轮加上一个判断只能顺着与第一轮不同的方向走。正确的做法是在dir数组中加入一个“方向来源”标记更简单的方式是第二轮时对cur点从它的“父方向”进行传递只沿垂直方向直线延伸。在我的实际项目中我会在入队时顺便记录每个点第一次访问到它时所用的方向然后第二轮搜索时限制方向为垂直于此方向的两个方向只有这样才能确保路径拐点不超过 2。否则你得到的 BFS 结果会错误地放过一些不符合规则的路径最终在老师人工验盘时当场翻车。3.3 直达、一拐、二拐的组合判定主控制函数的调度逻辑分层的搜索函数写好后你需要一个主控制函数来综合调度它们。这个主控函数是所有入口的统一收口无论是用户点击还是 AI 自动寻找最终都会调用它来判断“可不可消”。调度顺序上先调用is_line_empty判断直线连接失败后调用is_one_turn判断单拐再次失败后调用is_two_turn_bfs判断双拐。三层函数之间是短路求值的逻辑哪一层返回 1立即结束整个判断流程不再继续向下执行。组合判定代码的结构如下。int can_connect(int r1, int c1, int r2, int c2) { if (board[r1][c1] ! board[r2][c2]) return 0; // 类型不同直接 false if (r1 r2 c1 c2) return 0; // 同一个方块不能自消 // 层级 1直线 if (is_line_empty(r1, c1, r2, c2)) return 1; // 层级 2单拐 if (is_one_turn(r1, c1, r2, c2)) return 1; // 层级 3双拐BFS if (is_two_turn_bfs(r1, c1, r2, c2)) return 1; return 0; }主控函数的逻辑不算复杂但有三个至关重要的前置条件很容易被忽略。第一任意两个坐标方块的类型必须相同这个判断必须在路径搜索之前完成否则你很可能搜索出一条路径结果两端方块花色不一样白白浪费计算资源。第二两个坐标不能是同一个点这个判断看似多余但在 UI 交互中用户可能误点同一个方块两次如果不拦截is_line_empty会返回 1造成误消除。第三也是最隐蔽的board[r1][c1]本身不能为 0也就是说已经消除的位置不能再次被当作起点或终点参与匹配——一个空格子是不可能被消除的。有些同学在代码中只判断了类型相同忘了检查起点和终点本身是否为空格结果出现了“消除空气”的诡异 bug。4. 代码实现的骨架搭建从控制台到交互界面4.1 数据结构的统一定义与全局状态管理在一个完整的实验项目中代码的组织往往比算法本身更决定成败。很多同学的实验代码只有可怜的main函数加三个子函数看的人一头雾水写的人自己过两天也看不懂。为了给实验报告和答辩做准备最好把代码按职责分层数据层、算法层、交互层。数据层负责维护全局的棋盘状态数组和方块类型映射表算法层集中实现路径搜索的多个函数交互层负责接收用户输入、刷新界面、执行消除动作并触发胜利判定。typedef struct { int type; // 方块类型 1-5 int eliminated; // 0 表示存在1 表示已消除 } Block; typedef struct { Block cells[EXTEND_ROW][EXTEND_COL]; int remain_count; // 剩余未消除方块数量 int score; // 计分 } GameState; GameState game; void reset_game() { memset(game, 0, sizeof(game)); // 内部区域填充方块 for (int i 1; i ROW; i) { for (int j 1; j COL; j) { game.cells[i][j].type rand() % 5 1; game.cells[i][j].eliminated 0; game.remain_count; } } }Block结构体的设计体现了一个很好的抽象思维每个格子除了存类型还存一个“是否已被消除”的状态。为什么不用数组的值 0 来表示消除因为类型可能也用 0 表示空容易混。一旦类型和状态分离你就不需要担心语义重叠的问题。在算法层读取格子时统一检查eliminated字段在渲染层打印时根据eliminated决定打印方块图案还是空白区域。这种基于结构体的封装让代码的可读性提高了好几个档次。而全局状态管理上GameState结构体承担了所有全局状态的聚合。只要改变这个结构体整个游戏的状态就会同步更新不需要在各种函数之间传递大量的参数。这在程序规模变大时尤为有效。很多同学喜欢把棋盘数组、剩余个数、分数全部定义成独立的全局变量这在小型 Demo 中尚可但一旦要加入计时器、道具、悔棋等高级功能全局变量就会变成一团乱麻。把所有状态收拢到一个结构体里是新手向熟手过渡的关键一步。4.2 渲染与交互把控制台输出变成可玩的游戏循环如果实验允许使用图形界面建议优先选择简单的控制台 ANSI 图形或轻量级的图形库。控制台输出的方式是很多同学的首选因为它不需要搭建复杂的环境只需要在循环中不断清屏、打印当前棋盘状态就可以了。交互逻辑上等待用户输入两个方块的坐标调用can_connect判断如果返回 1 则执行消除动作并更新界面否则提示“无法连接”。void render_board() { system(cls); // Windows 环境清屏函数 printf( ); for (int c 1; c COL; c) printf(%4d , c); printf(\n); for (int i 1; i ROW; i) { printf(%3d , i); for (int j 1; j COL; j) { if (game.cells[i][j].eliminated) { printf( ·); // 空白占位符 } else { printf(%4d , game.cells[i][j].type); } } printf(\n); } printf(剩余方块数: %d\n, game.remain_count); } void game_loop() { int x1, y1, x2, y2; while (game.remain_count 0) { render_board(); printf(请输入第一个方块坐标 (row col): ); scanf(%d %d, x1, y1); printf(请输入第二个方块坐标 (row col): ); scanf(%d %d, x2, y2); if (can_connect(x1, y1, x2, y2)) { game.cells[x1][y1].eliminated 1; game.cells[x1][y1].type 0; game.cells[x2][y2].eliminated 1; game.cells[x2][y2].type 0; game.remain_count - 2; game.score 10; printf(消除成功当前得分%d\n, game.score); } else { printf(无法消除请重新选择。\n); } system(pause); // 防止界面闪退 } printf(恭喜通关最终得分%d\n, game.score); }这段代码的交互逻辑非常直观。scanf获取坐标后由can_connect统一判断成功后执行两个eliminated标记并更新剩余方块数。这里有一个通用做法需要提醒坐标输入的合法性检查不能省略。用户可能输入负数、超过棋盘范围的数甚至输入 0这些都会导致数组越界访问程序直接崩溃。代码中应该在can_connect判断之前增加一个if (x1 1 || x1 ROW || y1 1 || y1 COL || ...)的白名单校验。此外system(cls)在 Windows 下有效但在 Linux 下需要换成system(clear)如果你跨平台编译建议用宏定义预处理指令来区分平台。这不属于算法核心但绝对影响实验演示效果——如果你在答辩时用的是 Mac 电脑而代码里写着cls画面就会花成一片老师的第一印象会打折扣。4.3 消除后的连锁响应与死局检测机制连连看还有一个容易忽略的点死局检测。当棋盘上仍有方块但任意两个相同类型的方块都无法通过合法路径相连时游戏就进入了死局。大多数课程设计只要求做到判断两个方块不要求处理死局但如果你想让项目在答辩时脱颖而出把死局检测加上绝对是加分项。死局检测的朴素做法是遍历所有剩余方块对对每一对执行can_connect只要有一对可以消除立即返回“未死局”。时间复杂度在最坏情况下是 O(N^4)对 10x10 棋盘来说完全可接受。优化做法是用哈希表按方块类型分组只对类型相同的方块对进行判断这样检测速度会快很多。死局出现后比较稳妥的处理策略是给用户两个选项重新洗牌或者重新开局。洗牌操作指的是将棋盘上所有剩余的方块打乱重排但要保证每个类型的数量不变且洗出来的局面不是死局。int is_deadlock() { int type_count[6] {0}; // 假设类型为 1-5 for (int i 1; i ROW; i) { for (int j 1; j COL; j) { if (!game.cells[i][j].eliminated) { type_count[game.cells[i][j].type]; } } } for (int t 1; t 5; t) { if (type_count[t] 0) continue; // 收集所有类型为 t 的未消除点 Point pts[100]; int pn 0; for (int i 1; i ROW; i) { for (int j 1; j COL; j) { if (!game.cells[i][j].eliminated game.cells[i][j].type t) { pts[pn].row i; pts[pn].col j; pn; } } } for (int i 0; i pn; i) { for (int j i 1; j pn; j) { if (can_connect(pts[i].row, pts[i].col, pts[j].row, pts[j].col)) { return 0; // 发现一对可以消未死局 } } } } return 1; // 所有同类型对都不可消死局 }死局检测函数的存在让游戏的主循环必须多一层判断。每完成一次消除、刷新界面之前先调用is_deadlock检测。如果返回 1提示用户选择重新洗牌还是结束游戏。这套机制确保了用户不会面对一个“看起来还有方块却什么都点不动”的迷茫状态。很多商业连连看产品中死局自动洗牌是标配功能你的实验项目中哪怕只做一个手动触发按钮也足以体现你对用户体验的思考深度。5. 避坑指南连连看实验里 5 个让人抓狂的隐蔽问题5.1 拐点计数偏移用 BFS 时不记录方向导致误判现象明明两块方块之间需要拐三个弯程序却返回可以消除反过来有些只需要拐两个弯的路径反而判不出来。原因很多同学写着写着就把双拐 BFS 写成了“无限拐弯 BFS”因为 BFS 扩展时向四个方向同时扫描不加方向约束。第一轮从 A 出发向四个方向延伸第二轮又从第一轮得到的点向四个方向延伸这样搜索出来的路径实际上是无限制拐弯的你根本没有办法保证路径拐点数量不超过 2。解决给每个节点增加“来源方向”字段。初始化时A 点的来源方向为 -1第一轮扩展出的点记录它们的前进方向第二轮扩展时只沿着与来源方向垂直的两个方向继续扩展。同时需要在每一轮的目标检查中确认是否到达 B到达 B 即返回成功。如果你使用上述is_two_turn_bfs的朴素版本请务必手动打补丁加上方向限制。这个 bug 极其隐蔽普通的测试用例测不出来但一旦遇到拐了三次弯才连通的棋盘布局你的算法就翻车了。5.2 数组越界访问外围扩展后忘记同步修改所有函数现象棋盘初始化时明明留了一圈扩展边界但运行中偶尔出现莫名其妙的“额外方块”或者方块消失后无法再连接。原因你的外围扩展只改了init_board函数但is_line_empty、is_one_turn、is_two_turn_bfs函数里依然使用ROW和COL作为边界。循环变量从0到ROW会漏掉最边缘的一行导致边缘上的空白格子永远不被检测为可通行区域。解决检查全工程中所有涉及棋盘遍历的代码统一使用EXTEND_ROW和EXTEND_COL作为边界常量。同时保证所有循环的索引从0开始而不是从1开始因为扩展边界在0和EXTEND_ROW - 1。统一边界的使用对后续扩展功能有百利而无一害。这个“改一处忘一处”的错误在多人协作或复制粘贴代码时发生了无数次每换一次函数就要多检查一遍边界。5.3 死局误判与洗牌逻辑类型数量丢失导致无法通关现象游戏卡在死局状态但玩家明明还有可以消除的对子或者点击洗牌后棋盘上的方块种类数量变得不均匀出现最后剩两个相同方块但连接不上的死局。原因is_deadlock函数在统计类型数量时把已消除方块eliminated 1也算进去了导致误判。而洗牌逻辑在重新分配方块类型时没有严格统计当前剩余每种方块的数量而是用rand() % 5 1重新生成导致某些类型变多、某些类型变少。解决修正type_count统计逻辑只累加!eliminated的格子洗牌时先收集所有未消除方块的类型存入一个临时数组再用随机乱序算法如 Knuth 洗牌打乱这个数组最后按顺序重新填充到棋盘上未消除的位置。这样保证每种方块数量不变具有成为可完成局面的基本条件。另外洗牌后的新棋盘还要再次执行is_deadlock检测如果仍是死局则再次洗牌直到找到一个非死局面为止。这个循环理论上存在死循环的微小概率极稀疏棋盘可加一个最大重试次数超时后直接判定游戏结束。5.4 重复点击与快速消除交互层没有锁定状态现象玩家快速双击第二个方块时程序有时会连续消掉两个不同的对子导致计分错误或者在消除路径尚未绘制完成时棋盘状态处于中间态玩家点击到的坐标已经变化。原因在交互层没有引入“处理中”或“锁定”的概念。can_connect调用成功后需要立即标记两个方块为eliminated这个动作应该是原子的。如果你的代码在输出路径动画后才去修改eliminated那么在这段动画期间棋盘上的数据是未同步的玩家就能趁机点击到尚未消除的方块逻辑混乱。解决最简单的办法是在消除成功后立即将eliminated置为 1不等待动画完成。动画只是视觉渲染层面的效果不应该影响状态变更。在代码中设置一个全局标志位is_processing点击事件触发时先检查这个标志位如果为真则忽略本次输入。消除执行结束后再将标志位复位。这个小改动能让你的程序在快速点击下依然保持稳定。5.5 随机生成的方块数量不成对最后一对永远无法消除现象游戏运行到最后剩余方块的数量是奇数或者每种方块剩余数量是奇数导致无论如何都不可能全部消除。原因初始化棋盘时直接用了rand() % 5 1无脑填充没有保证每个类型出现的次数是偶数。连连看的规则决定每消一次必须移除两个相同类型的方块所有类型的总数必须为偶数否则游戏必然结束在死局状态。解决在初始化阶段生成两个相同类型的候选组交替放入棋盘。具体做法是计算总方块数ROW * COL确保它是偶数创建一个类型数组按顺序放入ROW * COL / 2对重复的类型值再用 Knuth 洗牌算法打乱最后填充到棋盘内部区域。这个方法既保证了每种类型数量成对也保证了方块分布的随机性。这是整个实验中最基础也最容易被忽视的点一旦前期没处理好后期无论算法多正确都无法通关。6. 把实验做成作品路径可视化、随机提示与答辩话术最后一个章节聊点能让你的实验从“能跑”变成“好看”的技巧。课程设计的评分标准通常包含两部分功能完整性和展示效果。功能完整性方面前五章已经覆盖展示效果方面你需要给评委看到你在细节上的投入。一个经验丰富的评委在五分钟的答辩时间内到底会关注什么他不会一行行读你的源码他只会做三件事运行程序看流畅度、随机点几下看是否有明显 bug、问你几个算法设计上的决策问题。路径可视化是最容易出彩的优化点。在控制台版本中当你判断出两个方块可以消除后不要立刻消除而是先把这条路径上的所有中间点用特殊符号比如*绘制出来停留几百毫秒再消除。这个视觉效果能非常直观地展示你的算法运行过程评委一看就知道你用的是“真算法”而不是“假遍历”。在is_two_turn_bfs中每找到一个有效中间点就把它的坐标存入一个临时数组路径确认后统一渲染。如果你使用图形界面库这就是在两点之间画一根折线的问题实现成本极低但视觉冲击力极强。同时这也能帮助你在调试时一眼看出路径搜索是否符合拐点约束。随机提示功能可以说是用户体验的点睛之笔。当玩家卡住的时候按 H 键随机选择一对可消除的方块并高亮显示这本质上是一次“重复调用is_deadlock并返回第一个可连接对”的操作。你可以用一个额外函数find_hint()遍历所有同类型的方块对返回第一对能够通过can_connect的坐标。在实际项目中光有这个功能还不够还需要把它和被卡住状态做一个联动如果is_deadlock()返回 1提示用户选择洗牌如果没有死局但用户连续多次无效点击说明他可能暂时找不到此时“向用户推荐一对”可以极大提升体验。这个细节在功能性实验中不加分但在工程化评估中绝对加分。至于答辩时的技术陈述核心有一条主线把二维数组当作图的存储底层把路径搜索当作图的遍历。答辩老师问到“非线性结构体现在哪”你可以说“棋盘中每个格子是图的一个节点格子的相邻关系是图的边路径搜索就是广度优先遍历的一种受限应用”。问到“为什么用 BFS 而不是 DFS”你可以说“BFS 天生保证找到最短路径满足拐点次数限制DFS 则可能找到过回路径导致误判”。这段话术能够把你的代码从“二维数组的遍历技巧”拔高到“非线性结构的应用”正好呼应实验标题。最后分享一下我自己做这个实验时的一个习惯永远在提交前做一轮“极限布局测试”。手动创建一个只有两个同类型方块、其余全空的棋盘确认它们能连接创建一个两个同类型方块被其他方块包围成环的棋盘确认它们不能连接创建一个充满随机方块但刻意让最后两个方块同类型的棋盘跑完整局确认不会出现无解局面。这三个极端测试用例通过基本能覆盖绝大多数隐藏问题。每次写完一个模块我都会先跑这三个用例再开始写下一个模块而不是全部写完再一次调。这个习惯帮我避开了无数个把自己绕晕的 bug。希望这些经验能帮到你让你的连连看实验不再只是应付差事而是成为一份真正拿得出手的作品。本文还有配套的精品资源点击获取
