简介武汉理工大学数据结构与算法综合实验以欢乐连连看游戏为载体完整演示了非线性结构二叉树、图、哈希表在真实项目中的落地方式以及DFS、BFS、动态规划等算法如何服务于消除路径判定和游戏逻辑优化。压缩包为7z格式共281个文件、226.97MB既包含Visual Studio解决方案LLK.sln、C源代码.cpp/.h、图像资源.bmp/.ico也保留了可运行的exe、编译中间文件.obj/.pdb与Git版本管理数据便于对照源码理解完整工程结构。已有2570人学习下载说明其在校内课程实验与期末设计中具有较高的参考价值。实验从棋盘建模到匹配判定均有明确工程结构对希望掌握非线性结构实际应用、提升算法编码能力的同学尤为适合可作为课程报告或答辩演示的完整参考。1. 欢乐连连看不只是消消乐非线性结构到底用到哪里把棋盘上两个长得一样的图块点掉看起来像一次“消消乐”但武汉理工数据结构实验里要求用非线性结构来落这个场景时事情就变了味——你需要想的不是“怎么连”而是先回答两个问题所有棋子之间的关系用什么组织两个棋子的通路用什么搜索第一个问题的答案通常是哈希表散列第二个问题的答案是非线性结构里的图邻接与遍历。欢乐连连看这个题目的经典做法是先把棋盘外扩一圈虚拟空位再把空中路径建模成带方向的图搜索用限制转折次数不超过 2 的 BFS 完成连通判定。这篇笔记按一条能直接交实验的路线写先讲清楚为什么这样建模再给出可以直接抄的 C / Python 代码最后是匹配索引、外圈空位和搜索变慢这些真实踩过的坑。适合正在被这个实验和数据结构期末复习一起夹击的同学照着复现。2. 棋盘建模与匹配索引先把非线性结构装进哈希表和图邻接2.1 用二维 int 数组存棋盘再扩一圈“-1”虚拟边界连连看有个容易被忽略的规则路径允许贴着棋盘边缘走。也就是说第一行棋子和最后一行棋子之间理论上可以绕到棋盘外再连起来。如果只用原始矩阵去判定第二行的障碍就会把两侧封死导致明明能消的棋子判成消不掉。我一般会先建一个扩展棋盘行数和列数各加 2内部把棋盘外的位置置为 -1棋盘内空位用 0棋子用正数类型编号。这样做的直接好处是边缘路径天然成为可搜索空间不需要为“越界”单独写一套特判。const int MAXN 25; int R, C; int g[MAXN][MAXN]; void initBoard(vectorvectorint raw) { R raw.size(); C raw[0].size(); memset(g, -1, sizeof(g)); for (int i 0; i R; i) for (int j 0; j C; j) g[i 1][j 1] raw[i][j]; // 正数表示棋子类型0 表示空格 }扩展之后的坐标从 1 到 R、1 到 C最外圈第 0 行、第 R1 行、第 0 列、第 C1 列全部是 -1。搜索代码里不再需要担心“走到边界数组越界”只需要让 BFS 的坐标范围覆盖 0..R1 和 0..C1。这个 -1 占位符也是后续判断空路径的关键只要不是棋子类型大于 0这一格从连通性角度就是可走的。2.2 同类型棋子索引用哈希表建立“类型 - 坐标列表”的非线性映射如果每一轮都在整个棋盘上暴力枚举所有棋子对棋盘是 10×10 还能忍到了 20×20 就开始明显卡顿。课程实验的隐藏评分点也在这里不能只会暴力枚举得体现出数据结构选型的意识。常见做法是建一个哈希表把每个棋子类型映射到坐标列表。之后判定可消时只需要拿当前棋子的类型 id 去查表取出同类型坐标做候选再对这些候选跑连通判定。unordered_mapint, vectorpairint, int type2pos; void rebuildIndex() { type2pos.clear(); for (int i 1; i R; i) for (int j 1; j C; j) if (g[i][j] 0) type2pos[g[i][j]].push_back({i, j}); }视频里很多学生只把二维数组当“棋盘”其实这个哈希索引才是实验里第一个非线性结构落点。它把原来 O(n²) 的匹配枚举降成 O(同类型数量²)棋盘越大收益越明显。如果关卡生成时保证每类棋子数量固定这个索引一次重建即可如果实现的是玩家手动消除模式则在每次成功消除后从对应 vector 里删掉坐标。2.3 非线性结构在实验里的真正落点把空白棋盘建模成图搜索数据结构课上讲非线性结构时树、图、哈希表是分开章节讲的。这个实验里它们会同时出现哈希表管匹配图管连通。难点在于并不是真的要像教科书那样先建一个邻接表再把边存进去而是把“空位之间的可达关系”当成一张隐式图。每个空格值 0 的格子是一个节点上下左右四个邻居如果也是空位或棋盘外就存在一条边棋子格子在未被消除前不能进入终点格例外。连通判定就变成图上带约束的最短路径搜索。struct Point { int r, c; }; struct SearchState { int r, c; int dir; // 0上 1下 2左 3右 int turns; // 已经转折次数 }; int dr[4] {-1, 1, 0, 0}; int dc[4] {0, 0, -1, 1};这样设计的好处是省内存不需要真正建出邻接表BFS 扩展时现场查上下左右四个方向即可。对实验报告来说这也是“非线性结构”最值得写的一段棋盘矩阵是线性存储的二维表但搜索语义是图遍历操作对象的组织方式是哈希索引三者各司其职。3. 相消判定从直线到两次转弯把可连规则拆成可直接抄的检测代码3.1 连连看的连通规则本质上是一次带约束的搜索连连看判定两个棋子能否消除规则可以压缩成三句话类型相同两个棋子之间能找到一条通路通路只由直线段组成转折次数不超过 2且不能穿过其他棋子。这个“不能穿过其他棋子”约束非常关键它在图搜索里等价于障碍物节点不可达。很多同学一上来就去写两层循环枚举中间转折点写完发现边界外路径、折点压在棋子上、转折次数算错各种问题。其实先按转折次数从少到多拆开把最基础的直连和一次转折写好再交给中级的扫线法或 BFS逻辑会清晰很多。3.2 直连同一行或同一列且中间无障碍直连是最简单的 case两个棋子的行坐标相等或列坐标相等且它们之间的所有格子都没有棋子。注意这里必须把两端排掉只检查开区间否则自己和自己比较会误判。bool betweenEmpty(int r1, int c1, int r2, int c2) { if (r1 r2) { int lo min(c1, c2), hi max(c1, c2); for (int c lo 1; c hi; c) if (g[r1][c] 0) return false; return true; } if (c1 c2) { int lo min(r1, r2), hi max(r1, r2); for (int r lo 1; r hi; r) if (g[r][c1] 0) return false; return true; } return false; }这段代码在扩展棋盘上运行所以 -1 边界不会被当成障碍0 空位也不会阻塞路径。直连是后续一切判定的地基一次转折和两次转折最终都要反复调用它所以建议把参数做成坐标对而不是绑定某个具体棋子结构体。3.3 一次转折两个候选折点本质是“先横后竖”或“先竖后横”一次转折的几何形式是一个 L 形路径。假设 A 和 B 两个点它们的行和列组合出两个候选折点p1 取 A 的行、B 的列p2 取 B 的行、A 的列。只要其中一个折点为空且 A 到折点、折点到 B 都是直连就说明可消。bool canLinkWithOneTurn(Point a, Point b) { Point p1 {a.r, b.c}; Point p2 {b.r, a.c}; if ((g[p1.r][p1.c] 0 || g[p1.r][p1.c] -1) betweenEmpty(a, p1) betweenEmpty(p1, b)) return true; if ((g[p2.r][p2.c] 0 || g[p2.r][p2.c] -1) betweenEmpty(a, p2) betweenEmpty(p2, b)) return true; return false; }这里有个容易翻车的边界p1 或 p2 可能恰好等于 A 或 B例如两个棋子同列时p1 的坐标就是 A 本身。虽然 betweenEmpty 对端点是开区间折点压在 A 上会导致路径退化成一条直线看起来无害但严格来说不能被当成 L 形路径。因此正确写法是先调用直连判定如果直连失败再对两个候选折点做“折点既不是 A 也不是 B、且折点处为空”的检查。3.4 两次转折扫线法的核心是先收集从 A、B 出发的直线可达点两次转折的路径形状像个 Z中间一定存在一条水平线或竖直线。更通用的判定思路是先从 A 出发沿上下左右四个方向直线扫描把所有连续可到达的空位收集成集合 SA再从 B 出发同样收集 SB。如果 SA 中某个点 p 和 SB 中某个点 q 在同一行或同一列且 p 到 q 之间没有棋子那 A 就能通过 p、q 到达 B。void collectReachable(Point s, int dir, vectorPoint res) { int nr s.r dr[dir]; int nc s.c dc[dir]; while (g[nr][nc] 0 || g[nr][nc] -1) { res.push_back({nr, nc}); nr dr[dir]; nc dc[dir]; } } bool canLinkWithTwoTurns(Point a, Point b) { vectorPoint SA, SB; for (int d 0; d 4; d) { collectReachable(a, d, SA); collectReachable(b, d, SB); } for (auto p : SA) for (auto q : SB) if ((p.r q.r || p.c q.c) betweenEmpty(p, q)) return true; return false; }这就是一个典型的“暴力枚举 剪枝”方案SA 和 SB 的规模都是 O(RC)双重循环最坏时是 O((RC)²)但小棋盘下可接受。这种先收集可达点再匹配中间直线的方法比盲目枚举全图上任意两个转折点要快很多也是很多现成连连看源码采用的实现路径。4. 用带方向的 BFS 统一处理两次转弯状态定义、剪枝与参数调整4.1 为什么用 BFS非线性结构上的图搜索比手写枚举更省心扫线法写起来很快但代码里容易漏掉一个隐含条件中间直线段必须在同一行或同一列且完全为空。一旦关卡尺寸变大、棋盘中有多个类型棋子混合手写枚举的维护成本会迅速上升。更通用、也更适合写进实验报告的方案是把问题直接归约为图上的最短路径搜索用 BFS 解决。BFS 天然能保证“第一次到达目标时转折次数最少”这与连连看“转折不超过 2”的规则完全对得上。BFS 每一步只向上下左右扩展天然不产生斜线穿越也不需要单独处理 L 形、Z 形等几何特例。递归改成迭代后还避免了 DFS 陷进一条深路导致转弯计数失控的问题。4.2 状态四维visited[r][c][dir][turns]少一维都会漏判最容易翻车的实现是用二维 visited 记录格子是否访问过。实际上同一个格子完全可以被访问多次它可能是以方向朝上、0 次转折到达的也可能是以方向朝右、2 次转折到达的。如果只记录二维坐标后面到达的高转弯状态会把前面低转弯状态覆盖掉或者反过来挡住后续扩展。正确的状态必须是四维行、列、当前方向、当前转折次数。方向之所以必须进状态是因为下一次移动是否增加转折次数取决于上一次方向是否相同。BFS 的完整实现如下。struct Node { int r, c; int dir; int turns; }; bool vis[MAXN][MAXN][4][3]; bool bfsLink(Point a, Point b, int maxTurn 2) { if (a.r b.r a.c b.c) return false; if (g[a.r][a.c] ! g[b.r][b.c]) return false; memset(vis, 0, sizeof(vis)); queueNode q; for (int d 0; d 4; d) { q.push({a.r, a.c, d, 0}); vis[a.r][a.c][d][0] true; } while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.r b.r cur.c b.c) return true; for (int nd 0; nd 4; nd) { if ((nd ^ 1) cur.dir) continue; int nr cur.r dr[nd]; int nc cur.c dc[nd]; if (nr 0 || nr R 1 || nc 0 || nc C 1) continue; if (!(nr b.r nc b.c) g[nr][nc] 0) continue; int nt cur.turns (nd ! cur.dir); if (nt maxTurn) continue; if (vis[nr][nc][nd][nt]) continue; vis[nr][nc][nd][nt] true; q.push({nr, nc, nd, nt}); } } return false; }这段代码的核心逻辑是起点先把四个方向都入队转折次数从 0 开始每个状态向外扩展时如果方向改变就加一次转折超过 maxTurn 就剪掉遇到其他棋子就挡住只有终点格允许落上去。(nd ^ 1) cur.dir是掉头剪枝因为往回走只会增加无效路径不会产生更优解。4.3 参数说明表maxTurn、外圈、终点特判分别怎么设参数取值作用maxTurn2连连看规则规定的最大转折次数外圈虚拟格-1允许路径沿棋盘外侧绕过障碍visited 第四维0..2记录转折次数区分同格不同状态初始入队方向0..3起点出发不计转折避免四个方向互相覆盖终点特判允许落在 g0 的格目标棋子本身作为终点不能当障碍如果把 maxTurn 改成 1BFS 就自动退化成一次转折判定改成 3 就是扩展版的“三折连连看”。这也是图搜索方案比手写多个 if 分支更优雅的地方规则变了只改参数不用重写逻辑。4.4 剪枝的三种姿势掉头剪、越界剪、同类型候选预剪BFS 在小棋盘上不慢但实验评测如果把棋盘开到 30×30 甚至更大就需要提前做剪枝。第一层剪枝是掉头剪已经在代码里实现了第二层是越界剪扩展前判断目标坐标是否仍在外圈范围内避免访问越界数组第三层是候选预剪也就是在调用 bfsLink 前先用 type2pos 索引过滤掉不可能匹配的棋子对。最值得加的是第三层如果某个类型只剩 1 个棋子它必然是死棋直接跳过如果两个棋子之间的距离已经超过 2 次转折能覆盖的“曼哈顿半径”也可以先排除。这些预处理不改变正确性但能让搜索调用次数下降一个数量级。5. 连连看实验踩坑排查外圈空位漏判、重复匹配与搜索变慢5.1 现象两个棋子明明能消程序却返回 false原因基本逃不出两个要么没建外圈虚拟格要么把起点或终点错误地当成障碍物。很多同学的第一个版本用原始矩阵判定边上的棋子想绕外圈路径时代码访问到边界外就直接越界或返回 false。解决方法是统一改成扩展棋盘所有判定都用偏移后的坐标。记住内部有效棋子放在 1..R、1..C外圈用 -1 表示。这样边界上的棋子天然拥有一条绕外圈的通路不需要在 BFS 里单独写“是否越界特判”。5.2 现象相邻的两个同类型棋子有时连不上有时又能连上这个问题我在调试时被折磨过一整晚。原因是起点状态初始化不一致如果只把起点的某一个方向入队而不是四个方向都入队就会漏掉某些起点的出发方向导致相邻棋子虽然能直连却因为方向状态没初始化而提前被剪掉。正确做法是起点的四个方向全部入队且 turns 都从 0 开始。展开 BFS 时再对每个状态做扩展。顺带提一句不要把“起点本身是棋子格”写进可通行判断里否则搜索刚开始就把自己挡住了。5.3 现象BFS 在 20×20 棋盘上跑出肉眼可见的卡顿大多数人第一反应是 BFS 太慢其实问题出在调用次数上每个棋子对都要跑一次完整 BFS20×20 棋盘可能有几百个同类型候选对每个 BFS 都要清空 visited 并入队大量状态累计起来自然慢。解决思路是先索引、后搜索。用 type2pos 拿到同类型坐标再优先对距离较近、通路截断可能性小的候选对调用 BFS。另外visited 数组用 memset 清零在全棋盘下也不便宜可以用“时间戳标记”代替每次重置。如果实验报告需要讲性能优化这两点足够写出一段有说服力的对比数据。5.4 现象消除后的棋子还能被匹配到点击后无响应这是哈希表索引没有同步更新造成的。棋盘上已经把棋子置成 0但 type2pos 里的坐标列表还残留着旧坐标。下一轮匹配时索引把已经消失的棋子也当成候选BFS 一看棋盘是空返回 true界面上却什么都没消。解决办法是在每次消除后同步删除索引里的对应坐标或者干脆在每轮操作后重建索引。棋盘不超过 20×20 时重建索引的代价很小实现也更不容易出错。// 消除后同步删除该坐标不要只改棋盘数组 auto vec type2pos[id]; vec.erase(remove_if(vec.begin(), vec.end(), [](const pairint, int p) { return p.first r p.second c; }), vec.end());如果用了引用别名 vec删除后不需要再写回 map因为 vector 本身还在 map 里。要是为了保证绝对简单也可以每次消除后直接调用 rebuildIndex()代价只是多扫一遍棋盘。5.5 现象转折次数计到 2却画出一条穿墙路径这个现象通常出现在手写扫线法的版本里。画路径时看起来是两条折线实际上某一段斜着穿过了棋子格或者三个折点不在同一行 / 同一列上。原因是对“转折点必须是空位”的检查用错了棋盘坐标比如直接用原始棋盘下标导致外圈折点被误判成越界。解决方法是把折点检查统一成先用 collectReachable 收集可达点再用 betweenEmpty 检查中间段最后才允许连线。不要把路径回显逻辑和判定逻辑混在一起判定只负责返回布尔值路径回显单独基于 BFS 的前驱状态回溯。6. 验证与提速手写边界测例、回显搜索路径、减少 BFS 调用6.1 先手工构造 5 组边界测例再谈正确性实验验收时最怕的不是大棋盘而是小棋盘里的边界条件。我习惯先手工构造几组 3×3 左右的极简棋盘测例棋盘状态期望结果测例 1第一行首尾各一个同类型棋子中间空格true测例 2两棋子同列但中间有阻挡false测例 3两个边角棋子中间有障碍可绕外圈一次折角true测例 4两个棋子类型不同false测例 5两个棋子相同坐标false把这几组测例直接写进主函数每次改动算法后都跑一遍。跑不过不是急着调 BFS而是先打印中间索引和外圈棋盘确认数据输入没在初始化阶段就错了。6.2 用前驱节点回溯路径验证搜索真的找到了“合法路径”说服自己“BFS 返回 true”还不够更稳妥的验证方式是直接把搜索路径打印出来。路径回溯需要在 BFS 入队时记录前驱状态这里同样需要四维数组。Node pre[MAXN][MAXN][4][3]; // BFS 入队前记录前驱 pre[nr][nc][nd][nt] cur; // 到达目标后从终点状态回溯到起点 vectorPoint path; Node s cur; while (!(s.r a.r s.c a.c)) { path.push_back({s.r, s.c}); s pre[s.r][s.c][s.dir][s.turns]; } reverse(path.begin(), path.end());回溯时注意起点可能以四个方向中的任意一个被初始化所以终止条件只判断行和列不要同时要求方向等于某个固定值。把 path 里的坐标逐段画出来检查每段是否同轴、转折次数是否小于等于 2这才是对“可消”最直接的证明。6.3 提速顺序先通用 BFS再索引预剪最后才考虑换算法我的习惯是先跑通用 BFS 保证正确性再优化候选集不在一开始就引入 A* 这类带估价的搜索。40×40 以下的棋盘四维 BFS 加掉头剪枝已经足够应对绝大多数关卡。真正值得做的是减少 BFS 调用次数每次点击后先查 type2pos从同类型坐标里挑候选再用“曼哈顿距离 类型剩余数量”过滤。这样做以后BFS 的调用量通常能降一半以上。我自己写这个实验时最大的教训是不要觉得 BFS 简单就跳过状态维度的设计。只记录坐标的版本跑出过诡异漏判加回 dir 和 turns 后一次性全过。这个坑踩过一次就记住了现在每次交付前也会先跑一遍边界测例再交。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/28 13:05:02 · 阅读 1.2k 连连看实验中的非线性结构与BFS搜索实现详解
简介武汉理工大学数据结构与算法综合实验以欢乐连连看游戏为载体完整演示了非线性结构二叉树、图、哈希表在真实项目中的落地方式以及DFS、BFS、动态规划等算法如何服务于消除路径判定和游戏逻辑优化。压缩包为7z格式共281个文件、226.97MB既包含Visual Studio解决方案LLK.sln、C源代码.cpp/.h、图像资源.bmp/.ico也保留了可运行的exe、编译中间文件.obj/.pdb与Git版本管理数据便于对照源码理解完整工程结构。已有2570人学习下载说明其在校内课程实验与期末设计中具有较高的参考价值。实验从棋盘建模到匹配判定均有明确工程结构对希望掌握非线性结构实际应用、提升算法编码能力的同学尤为适合可作为课程报告或答辩演示的完整参考。1. 欢乐连连看不只是消消乐非线性结构到底用到哪里把棋盘上两个长得一样的图块点掉看起来像一次“消消乐”但武汉理工数据结构实验里要求用非线性结构来落这个场景时事情就变了味——你需要想的不是“怎么连”而是先回答两个问题所有棋子之间的关系用什么组织两个棋子的通路用什么搜索第一个问题的答案通常是哈希表散列第二个问题的答案是非线性结构里的图邻接与遍历。欢乐连连看这个题目的经典做法是先把棋盘外扩一圈虚拟空位再把空中路径建模成带方向的图搜索用限制转折次数不超过 2 的 BFS 完成连通判定。这篇笔记按一条能直接交实验的路线写先讲清楚为什么这样建模再给出可以直接抄的 C / Python 代码最后是匹配索引、外圈空位和搜索变慢这些真实踩过的坑。适合正在被这个实验和数据结构期末复习一起夹击的同学照着复现。2. 棋盘建模与匹配索引先把非线性结构装进哈希表和图邻接2.1 用二维 int 数组存棋盘再扩一圈“-1”虚拟边界连连看有个容易被忽略的规则路径允许贴着棋盘边缘走。也就是说第一行棋子和最后一行棋子之间理论上可以绕到棋盘外再连起来。如果只用原始矩阵去判定第二行的障碍就会把两侧封死导致明明能消的棋子判成消不掉。我一般会先建一个扩展棋盘行数和列数各加 2内部把棋盘外的位置置为 -1棋盘内空位用 0棋子用正数类型编号。这样做的直接好处是边缘路径天然成为可搜索空间不需要为“越界”单独写一套特判。const int MAXN 25; int R, C; int g[MAXN][MAXN]; void initBoard(vectorvectorint raw) { R raw.size(); C raw[0].size(); memset(g, -1, sizeof(g)); for (int i 0; i R; i) for (int j 0; j C; j) g[i 1][j 1] raw[i][j]; // 正数表示棋子类型0 表示空格 }扩展之后的坐标从 1 到 R、1 到 C最外圈第 0 行、第 R1 行、第 0 列、第 C1 列全部是 -1。搜索代码里不再需要担心“走到边界数组越界”只需要让 BFS 的坐标范围覆盖 0..R1 和 0..C1。这个 -1 占位符也是后续判断空路径的关键只要不是棋子类型大于 0这一格从连通性角度就是可走的。2.2 同类型棋子索引用哈希表建立“类型 - 坐标列表”的非线性映射如果每一轮都在整个棋盘上暴力枚举所有棋子对棋盘是 10×10 还能忍到了 20×20 就开始明显卡顿。课程实验的隐藏评分点也在这里不能只会暴力枚举得体现出数据结构选型的意识。常见做法是建一个哈希表把每个棋子类型映射到坐标列表。之后判定可消时只需要拿当前棋子的类型 id 去查表取出同类型坐标做候选再对这些候选跑连通判定。unordered_mapint, vectorpairint, int type2pos; void rebuildIndex() { type2pos.clear(); for (int i 1; i R; i) for (int j 1; j C; j) if (g[i][j] 0) type2pos[g[i][j]].push_back({i, j}); }视频里很多学生只把二维数组当“棋盘”其实这个哈希索引才是实验里第一个非线性结构落点。它把原来 O(n²) 的匹配枚举降成 O(同类型数量²)棋盘越大收益越明显。如果关卡生成时保证每类棋子数量固定这个索引一次重建即可如果实现的是玩家手动消除模式则在每次成功消除后从对应 vector 里删掉坐标。2.3 非线性结构在实验里的真正落点把空白棋盘建模成图搜索数据结构课上讲非线性结构时树、图、哈希表是分开章节讲的。这个实验里它们会同时出现哈希表管匹配图管连通。难点在于并不是真的要像教科书那样先建一个邻接表再把边存进去而是把“空位之间的可达关系”当成一张隐式图。每个空格值 0 的格子是一个节点上下左右四个邻居如果也是空位或棋盘外就存在一条边棋子格子在未被消除前不能进入终点格例外。连通判定就变成图上带约束的最短路径搜索。struct Point { int r, c; }; struct SearchState { int r, c; int dir; // 0上 1下 2左 3右 int turns; // 已经转折次数 }; int dr[4] {-1, 1, 0, 0}; int dc[4] {0, 0, -1, 1};这样设计的好处是省内存不需要真正建出邻接表BFS 扩展时现场查上下左右四个方向即可。对实验报告来说这也是“非线性结构”最值得写的一段棋盘矩阵是线性存储的二维表但搜索语义是图遍历操作对象的组织方式是哈希索引三者各司其职。3. 相消判定从直线到两次转弯把可连规则拆成可直接抄的检测代码3.1 连连看的连通规则本质上是一次带约束的搜索连连看判定两个棋子能否消除规则可以压缩成三句话类型相同两个棋子之间能找到一条通路通路只由直线段组成转折次数不超过 2且不能穿过其他棋子。这个“不能穿过其他棋子”约束非常关键它在图搜索里等价于障碍物节点不可达。很多同学一上来就去写两层循环枚举中间转折点写完发现边界外路径、折点压在棋子上、转折次数算错各种问题。其实先按转折次数从少到多拆开把最基础的直连和一次转折写好再交给中级的扫线法或 BFS逻辑会清晰很多。3.2 直连同一行或同一列且中间无障碍直连是最简单的 case两个棋子的行坐标相等或列坐标相等且它们之间的所有格子都没有棋子。注意这里必须把两端排掉只检查开区间否则自己和自己比较会误判。bool betweenEmpty(int r1, int c1, int r2, int c2) { if (r1 r2) { int lo min(c1, c2), hi max(c1, c2); for (int c lo 1; c hi; c) if (g[r1][c] 0) return false; return true; } if (c1 c2) { int lo min(r1, r2), hi max(r1, r2); for (int r lo 1; r hi; r) if (g[r][c1] 0) return false; return true; } return false; }这段代码在扩展棋盘上运行所以 -1 边界不会被当成障碍0 空位也不会阻塞路径。直连是后续一切判定的地基一次转折和两次转折最终都要反复调用它所以建议把参数做成坐标对而不是绑定某个具体棋子结构体。3.3 一次转折两个候选折点本质是“先横后竖”或“先竖后横”一次转折的几何形式是一个 L 形路径。假设 A 和 B 两个点它们的行和列组合出两个候选折点p1 取 A 的行、B 的列p2 取 B 的行、A 的列。只要其中一个折点为空且 A 到折点、折点到 B 都是直连就说明可消。bool canLinkWithOneTurn(Point a, Point b) { Point p1 {a.r, b.c}; Point p2 {b.r, a.c}; if ((g[p1.r][p1.c] 0 || g[p1.r][p1.c] -1) betweenEmpty(a, p1) betweenEmpty(p1, b)) return true; if ((g[p2.r][p2.c] 0 || g[p2.r][p2.c] -1) betweenEmpty(a, p2) betweenEmpty(p2, b)) return true; return false; }这里有个容易翻车的边界p1 或 p2 可能恰好等于 A 或 B例如两个棋子同列时p1 的坐标就是 A 本身。虽然 betweenEmpty 对端点是开区间折点压在 A 上会导致路径退化成一条直线看起来无害但严格来说不能被当成 L 形路径。因此正确写法是先调用直连判定如果直连失败再对两个候选折点做“折点既不是 A 也不是 B、且折点处为空”的检查。3.4 两次转折扫线法的核心是先收集从 A、B 出发的直线可达点两次转折的路径形状像个 Z中间一定存在一条水平线或竖直线。更通用的判定思路是先从 A 出发沿上下左右四个方向直线扫描把所有连续可到达的空位收集成集合 SA再从 B 出发同样收集 SB。如果 SA 中某个点 p 和 SB 中某个点 q 在同一行或同一列且 p 到 q 之间没有棋子那 A 就能通过 p、q 到达 B。void collectReachable(Point s, int dir, vectorPoint res) { int nr s.r dr[dir]; int nc s.c dc[dir]; while (g[nr][nc] 0 || g[nr][nc] -1) { res.push_back({nr, nc}); nr dr[dir]; nc dc[dir]; } } bool canLinkWithTwoTurns(Point a, Point b) { vectorPoint SA, SB; for (int d 0; d 4; d) { collectReachable(a, d, SA); collectReachable(b, d, SB); } for (auto p : SA) for (auto q : SB) if ((p.r q.r || p.c q.c) betweenEmpty(p, q)) return true; return false; }这就是一个典型的“暴力枚举 剪枝”方案SA 和 SB 的规模都是 O(RC)双重循环最坏时是 O((RC)²)但小棋盘下可接受。这种先收集可达点再匹配中间直线的方法比盲目枚举全图上任意两个转折点要快很多也是很多现成连连看源码采用的实现路径。4. 用带方向的 BFS 统一处理两次转弯状态定义、剪枝与参数调整4.1 为什么用 BFS非线性结构上的图搜索比手写枚举更省心扫线法写起来很快但代码里容易漏掉一个隐含条件中间直线段必须在同一行或同一列且完全为空。一旦关卡尺寸变大、棋盘中有多个类型棋子混合手写枚举的维护成本会迅速上升。更通用、也更适合写进实验报告的方案是把问题直接归约为图上的最短路径搜索用 BFS 解决。BFS 天然能保证“第一次到达目标时转折次数最少”这与连连看“转折不超过 2”的规则完全对得上。BFS 每一步只向上下左右扩展天然不产生斜线穿越也不需要单独处理 L 形、Z 形等几何特例。递归改成迭代后还避免了 DFS 陷进一条深路导致转弯计数失控的问题。4.2 状态四维visited[r][c][dir][turns]少一维都会漏判最容易翻车的实现是用二维 visited 记录格子是否访问过。实际上同一个格子完全可以被访问多次它可能是以方向朝上、0 次转折到达的也可能是以方向朝右、2 次转折到达的。如果只记录二维坐标后面到达的高转弯状态会把前面低转弯状态覆盖掉或者反过来挡住后续扩展。正确的状态必须是四维行、列、当前方向、当前转折次数。方向之所以必须进状态是因为下一次移动是否增加转折次数取决于上一次方向是否相同。BFS 的完整实现如下。struct Node { int r, c; int dir; int turns; }; bool vis[MAXN][MAXN][4][3]; bool bfsLink(Point a, Point b, int maxTurn 2) { if (a.r b.r a.c b.c) return false; if (g[a.r][a.c] ! g[b.r][b.c]) return false; memset(vis, 0, sizeof(vis)); queueNode q; for (int d 0; d 4; d) { q.push({a.r, a.c, d, 0}); vis[a.r][a.c][d][0] true; } while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.r b.r cur.c b.c) return true; for (int nd 0; nd 4; nd) { if ((nd ^ 1) cur.dir) continue; int nr cur.r dr[nd]; int nc cur.c dc[nd]; if (nr 0 || nr R 1 || nc 0 || nc C 1) continue; if (!(nr b.r nc b.c) g[nr][nc] 0) continue; int nt cur.turns (nd ! cur.dir); if (nt maxTurn) continue; if (vis[nr][nc][nd][nt]) continue; vis[nr][nc][nd][nt] true; q.push({nr, nc, nd, nt}); } } return false; }这段代码的核心逻辑是起点先把四个方向都入队转折次数从 0 开始每个状态向外扩展时如果方向改变就加一次转折超过 maxTurn 就剪掉遇到其他棋子就挡住只有终点格允许落上去。(nd ^ 1) cur.dir是掉头剪枝因为往回走只会增加无效路径不会产生更优解。4.3 参数说明表maxTurn、外圈、终点特判分别怎么设参数取值作用maxTurn2连连看规则规定的最大转折次数外圈虚拟格-1允许路径沿棋盘外侧绕过障碍visited 第四维0..2记录转折次数区分同格不同状态初始入队方向0..3起点出发不计转折避免四个方向互相覆盖终点特判允许落在 g0 的格目标棋子本身作为终点不能当障碍如果把 maxTurn 改成 1BFS 就自动退化成一次转折判定改成 3 就是扩展版的“三折连连看”。这也是图搜索方案比手写多个 if 分支更优雅的地方规则变了只改参数不用重写逻辑。4.4 剪枝的三种姿势掉头剪、越界剪、同类型候选预剪BFS 在小棋盘上不慢但实验评测如果把棋盘开到 30×30 甚至更大就需要提前做剪枝。第一层剪枝是掉头剪已经在代码里实现了第二层是越界剪扩展前判断目标坐标是否仍在外圈范围内避免访问越界数组第三层是候选预剪也就是在调用 bfsLink 前先用 type2pos 索引过滤掉不可能匹配的棋子对。最值得加的是第三层如果某个类型只剩 1 个棋子它必然是死棋直接跳过如果两个棋子之间的距离已经超过 2 次转折能覆盖的“曼哈顿半径”也可以先排除。这些预处理不改变正确性但能让搜索调用次数下降一个数量级。5. 连连看实验踩坑排查外圈空位漏判、重复匹配与搜索变慢5.1 现象两个棋子明明能消程序却返回 false原因基本逃不出两个要么没建外圈虚拟格要么把起点或终点错误地当成障碍物。很多同学的第一个版本用原始矩阵判定边上的棋子想绕外圈路径时代码访问到边界外就直接越界或返回 false。解决方法是统一改成扩展棋盘所有判定都用偏移后的坐标。记住内部有效棋子放在 1..R、1..C外圈用 -1 表示。这样边界上的棋子天然拥有一条绕外圈的通路不需要在 BFS 里单独写“是否越界特判”。5.2 现象相邻的两个同类型棋子有时连不上有时又能连上这个问题我在调试时被折磨过一整晚。原因是起点状态初始化不一致如果只把起点的某一个方向入队而不是四个方向都入队就会漏掉某些起点的出发方向导致相邻棋子虽然能直连却因为方向状态没初始化而提前被剪掉。正确做法是起点的四个方向全部入队且 turns 都从 0 开始。展开 BFS 时再对每个状态做扩展。顺带提一句不要把“起点本身是棋子格”写进可通行判断里否则搜索刚开始就把自己挡住了。5.3 现象BFS 在 20×20 棋盘上跑出肉眼可见的卡顿大多数人第一反应是 BFS 太慢其实问题出在调用次数上每个棋子对都要跑一次完整 BFS20×20 棋盘可能有几百个同类型候选对每个 BFS 都要清空 visited 并入队大量状态累计起来自然慢。解决思路是先索引、后搜索。用 type2pos 拿到同类型坐标再优先对距离较近、通路截断可能性小的候选对调用 BFS。另外visited 数组用 memset 清零在全棋盘下也不便宜可以用“时间戳标记”代替每次重置。如果实验报告需要讲性能优化这两点足够写出一段有说服力的对比数据。5.4 现象消除后的棋子还能被匹配到点击后无响应这是哈希表索引没有同步更新造成的。棋盘上已经把棋子置成 0但 type2pos 里的坐标列表还残留着旧坐标。下一轮匹配时索引把已经消失的棋子也当成候选BFS 一看棋盘是空返回 true界面上却什么都没消。解决办法是在每次消除后同步删除索引里的对应坐标或者干脆在每轮操作后重建索引。棋盘不超过 20×20 时重建索引的代价很小实现也更不容易出错。// 消除后同步删除该坐标不要只改棋盘数组 auto vec type2pos[id]; vec.erase(remove_if(vec.begin(), vec.end(), [](const pairint, int p) { return p.first r p.second c; }), vec.end());如果用了引用别名 vec删除后不需要再写回 map因为 vector 本身还在 map 里。要是为了保证绝对简单也可以每次消除后直接调用 rebuildIndex()代价只是多扫一遍棋盘。5.5 现象转折次数计到 2却画出一条穿墙路径这个现象通常出现在手写扫线法的版本里。画路径时看起来是两条折线实际上某一段斜着穿过了棋子格或者三个折点不在同一行 / 同一列上。原因是对“转折点必须是空位”的检查用错了棋盘坐标比如直接用原始棋盘下标导致外圈折点被误判成越界。解决方法是把折点检查统一成先用 collectReachable 收集可达点再用 betweenEmpty 检查中间段最后才允许连线。不要把路径回显逻辑和判定逻辑混在一起判定只负责返回布尔值路径回显单独基于 BFS 的前驱状态回溯。6. 验证与提速手写边界测例、回显搜索路径、减少 BFS 调用6.1 先手工构造 5 组边界测例再谈正确性实验验收时最怕的不是大棋盘而是小棋盘里的边界条件。我习惯先手工构造几组 3×3 左右的极简棋盘测例棋盘状态期望结果测例 1第一行首尾各一个同类型棋子中间空格true测例 2两棋子同列但中间有阻挡false测例 3两个边角棋子中间有障碍可绕外圈一次折角true测例 4两个棋子类型不同false测例 5两个棋子相同坐标false把这几组测例直接写进主函数每次改动算法后都跑一遍。跑不过不是急着调 BFS而是先打印中间索引和外圈棋盘确认数据输入没在初始化阶段就错了。6.2 用前驱节点回溯路径验证搜索真的找到了“合法路径”说服自己“BFS 返回 true”还不够更稳妥的验证方式是直接把搜索路径打印出来。路径回溯需要在 BFS 入队时记录前驱状态这里同样需要四维数组。Node pre[MAXN][MAXN][4][3]; // BFS 入队前记录前驱 pre[nr][nc][nd][nt] cur; // 到达目标后从终点状态回溯到起点 vectorPoint path; Node s cur; while (!(s.r a.r s.c a.c)) { path.push_back({s.r, s.c}); s pre[s.r][s.c][s.dir][s.turns]; } reverse(path.begin(), path.end());回溯时注意起点可能以四个方向中的任意一个被初始化所以终止条件只判断行和列不要同时要求方向等于某个固定值。把 path 里的坐标逐段画出来检查每段是否同轴、转折次数是否小于等于 2这才是对“可消”最直接的证明。6.3 提速顺序先通用 BFS再索引预剪最后才考虑换算法我的习惯是先跑通用 BFS 保证正确性再优化候选集不在一开始就引入 A* 这类带估价的搜索。40×40 以下的棋盘四维 BFS 加掉头剪枝已经足够应对绝大多数关卡。真正值得做的是减少 BFS 调用次数每次点击后先查 type2pos从同类型坐标里挑候选再用“曼哈顿距离 类型剩余数量”过滤。这样做以后BFS 的调用量通常能降一半以上。我自己写这个实验时最大的教训是不要觉得 BFS 简单就跳过状态维度的设计。只记录坐标的版本跑出过诡异漏判加回 dir 和 turns 后一次性全过。这个坑踩过一次就记住了现在每次交付前也会先跑一遍边界测例再交。希望帮到你。本文还有配套的精品资源点击获取