企业官网建设流程全解析

简介：一份完整的武汉理工大学数据结构与算法综合实验连连看游戏开发报告，面向学习数据结构与算法、C++及MFC框架的本科生，主要用于课程设计或综合实践参考。压缩包内包含1个docx文档，大小约1.37MB，内容涵盖实验目的与要求、需求分析、二维数组数据结构设计、三种消子判断算法（一条直线、两条直线、三条直线连通）的详细流程与C++代码实现、胜负判断、提示、重排、计时及游戏模式设计，并展示了使用MFC Dialog和GDI编程构建图形界面的思路。报告中对三种连通算法的路径搜索以及用栈保存关键点均有详细讲解，并配有可运行代码片段，读者可直接对照使用或在此基础上扩展关卡模式。报告还融入了软件工程化思维，从系统需求分析到迭代开发均有说明。目前已有227人学习，适合需要完成连连看课程设计或想深入理解数组、栈及连通算法应用的读者参考。

1. 从“连连看”实验要求看数据结构课设的真实考点

“武汉理工大学数据结构与算法综合实验连连看”这个标题，看起来只是一门 C 语言课的期末大作业，但放在编程能力和面试的语境里，它是数据结构和算法综合能力最典型的压力测试。连连看这个选题不是让你做一个娱乐产品，而是要你用数据结构和算法把“棋盘建模、图案匹配、连通路径搜索、死局检测、自动求解”这一整条链路打通。很多 5 年以上开发者也未必能在半小时内写出一个无死锁的消除判定。它考察的核心不是界面，而是三件事：如何抽象棋盘状态，如何把“拐弯不超过两次”翻译成搜索算法，以及如何控制最坏情况下的复杂度。这篇文章就从这三个维度，把这条链路拆开讲清楚。

2. 棋盘与消除：连连看底层数据结构从二维数组到状态机

有人看到“综合实验”四个字，上来就画 UML 类图，设计了一堆抽象接口，最后代码没写几行，反而被自己的架构套住。数据结构实验最忌讳过度设计。连连看的棋盘是一个天然的二维网格，最直接的数据结构就是二维数组，但真正决定代码质量的，是你怎么用状态机去管理消除过程。

2.1 为什么二维数组依然是成本最低的棋盘模型

连连看的棋盘在逻辑上是一个ROWS × COLS的矩阵，每个单元格的值表示一种图案，空位用 0 表示。二维数组让随机访问的时间复杂度是 O(1)，内存连续、缓存利用率高，这在路径搜索里非常关键——因为你会在短时间内反复读取相邻格子。

有些同学为了展示“高级”数据结构，把棋盘设计成邻接表图结构，每个格子是一个 Node 对象，记录了上下左右四个指针。这个方案在理论课上可以讲，但在实际操作里是给自己挖坑：你需要额外处理节点生命周期，路径搜索时指针跳转的局部性也很差。除非棋盘是稀疏的，否则没有理由放弃顺序存储。

另一个常见误区是把“格子值”和“格子状态”混在一个变量里。比如用board[r][c] = -1表示已消除，用0表示空位。听起来没问题，但当你写“剩余图案数量”统计时，就要小心-1和0的语义冲突。我的做法是棋盘只存图案值（0 表示空），需要记录“已消除”等额外状态时，再开一个同尺寸的bool数组。空间换清晰度，很划算。

在代码实现上，推荐用一维数组配合下标计算来模拟二维。这样做的好处是：如果需要把棋盘状态存档或做网络传输，可以直接对整个一维数组做 memcpy；如果做“棋盘镜像”或“旋转”，也只处理一段连续内存。

2.2 消除条件的状态机：从“两个相同”到“三态校验”

很多第一次写连连看的同学，把消除判断写成“两个格子图案相同就直接消掉”。这忽略了连连看真正的规则：图案相同只是必要条件，还必须存在一条拐弯不超过两次、且不经过任何非空格子的路径。

所以这里需要一个状态机，流程是：

1. 检查两个坐标是否越界；
2. 检查两个格子是否都是有效图案（非空）；
3. 检查两个格子的图案值是否相等；
4. 调用路径搜索算法，检查二者之间是否存在合法路径；
5. 如果路径合法，把两个格子置空，否则返回失败。

这个流程里的第 4 步是最耗时的。如果你在 UI 层每点击一次都做一次全盘扫描，那会非常卡。正确做法是把路径搜索独立成函数，并且加上一层短路判断：如果两个格子相邻，直接返回 true；如果两个格子在同一行或同一列，先检查中间是否全部为空。

2.3 数据结构的扩展：如果要写存档和回放

实验报告如果想拿高分，通常会加“历史记录”或“回放”功能。这时候数据结构就要开始扩展了。我的建议是不要马上引入链表或树，先用一个动态数组保存每一步的棋盘快照：

struct Step { int board[MAX_ROWS][MAX_COLS]; int r1, c1, r2, c2; }; vector<Step> history;

这是“时间换空间”的典型设计。每一步保存整个棋盘，内存占用是每一步 100 字节 × 总步数，一个 200 步的游戏也就 20KB 左右，完全可接受。比维护增量补丁要简单得多，而且回放时只需要依次恢复快照。

如果你还希望支持“撤销”，那更简单了：把当前状态压栈，撤销时从栈里弹出上一份快照。在设计上，快照类最好实现serialize和deserialize方法，这样存档可以落盘，回放也可以从磁盘开始。

下表是棋盘几种建模方式的选型对比：

2.4 棋盘初始化与洗牌的代码实现

棋盘初始化看起来很简单，实际上有一个隐藏要求：每种图案的出现次数必须是偶数，否则最后一定会有无法消除的“孤子”。所以不能直接随机填充，而是先构造一个图案池，再打乱顺序。

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <string.h> #define ROWS 10 #define COLS 12 #define TYPES 6 int board[ROWS][COLS]; void init_board(int rows, int cols, int types) { int total = rows * cols; // 图案池：保证每个图案出现次数为偶数 int *pool = (int*)malloc(sizeof(int) * total); for (int i = 0; i < total; i++) { pool[i] = (i % types) + 1; // 1 到 types，0 保留给空位 } // Fisher-Yates 洗牌 srand((unsigned int)time(NULL)); for (int i = total - 1; i > 0; i--) { int j = rand() % (i + 1); int tmp = pool[i]; pool[i] = pool[j]; pool[j] = tmp; } // 一维池子转二维棋盘 int idx = 0; for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { board[r][c] = pool[idx++]; } } free(pool); }

这段代码有几个细节需要说明。第一，pool[i] = (i % types) + 1保证了图案按 1 到 6 循环，总数 120 个格子，每个图案恰好 20 个，天然是偶数。第二，洗牌用的是 Fisher-Yates，它是无偏的，每个图案分布都等概率；不要用rand() % total反复交换，那会引入偏差。第三，这里刻意把 0 留空位，棋盘上的图案值从 1 开始，逻辑层判断时就用board[r][c] != 0来判定是否为空。

3. 连通性判定与路径搜索：把“最多拐两次”翻译成算法

这一章是连连看真正的核心算法部分。消除判定里最难的不是“图案相同”，而是“存在一条符合条件的连通路径”。把两个差不多的格子消掉，背后藏着一个经典问题：在网格图中求一个拐弯次数受限的路径。

3.1 形式化：直线、单拐点与双拐点

把连连看的路径规则形式化，可以分成三种情况。

第一种是直线路径。两个格子在同一行，且中间所有格子都为空；或者两个格子在同一列，中间所有格子都为空。这种情况不需要搜索，直接检查线段上的每个单元格即可。

第二种是单拐点路径。两个格子的连线构成一个直角，拐点出现在“以这两个点为对角顶点的矩形”的另外两个角之一。也就是如果起点是(r1, c1)，终点是(r2, c2)，那么潜在拐点只有两个：(r1, c2)和(r2, c1)。检查的方法是确保拐点本身是空位，并且起点到拐点、拐点到终点这两条线段都畅通。

第三种是双拐点路径。路径形状是一个“Z”字形，或者更复杂一点，两个拐点分布在两条平行的水平线或垂直线上。如果两个格子既不在同一行也不在同一列，双拐点路径可以看作：先让一条线段从起点延伸到某个中间行r_k，然后水平移动到终点的列，再垂直到达终点。枚举所有可能的r_k和c_k即可。

有一个细节容易被忽略：很多实现允许路径从棋盘的外围边界绕过去，也就是把棋盘外圈当作空位。比如起点在左下角，终点在右上角，路径可以贴着棋盘外圈走。解决方法是把整个棋盘逻辑上扩展一圈空位，搜索时索引范围从[-1, ROWS]和[-1, COLS]扩大。在 C 数组里，这通常用“坐标值平移”实现：actor_r = r + 1，actor_c = c + 1，在逻辑坐标上搜索。

3.2 用 BFS 把“拐弯次数”当成路径代价

分情况枚举适合标准规则，但如果想统一处理“最多拐 N 次”的变体，或者想实现一个更优雅的框架，BFS 会更好。BFS 状态里不再只记录坐标，而是记录“方向”和“拐弯次数”，这样可以对拐弯次数做一个最短路搜索。

from collections import deque def has_path(board, r1, c1, r2, c2, max_turns=2): """判断两点之间是否存在拐弯不超过 max_turns 次的路径""" rows, cols = len(board), len(board[0]) # 四个方向：上、下、左、右 dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)] # visited[turns][r][c] visited = set() # 队列里存 (行, 列, 方向, 拐弯次数) q = deque() # 起点可以向四个方向出发，初始不算拐弯 for d in range(4): dr, dc = dirs[d] visited.add((r1, c1, d, 0)) q.append((r1, c1, d, 0, [])) while q: r, c, direction, turns, path = q.popleft() # 到达终点，且拐弯次数不超过限制 if (r, c) == (r2, c2): return True for nd in range(4): dr, dc = dirs[nd] nr, nc = r + dr, c + dc # 检查边界 if not (0 <= nr < rows and 0 <= nc < cols): continue # 不能走到非空格子（除非是终点） if board[nr][nc] != 0 and (nr, nc) != (r2, c2): continue # 计算新拐弯次数 new_turns = turns if nd == direction else turns + 1 if new_turns > max_turns: continue state = (nr, nc, nd, new_turns) if state in visited: continue visited.add(state) q.append((nr, nc, nd, new_turns, path + [(nr, nc)])) return False

这段 BFS 代码有几点值得注意。第一，状态里包含了“方向”和“累计拐弯次数”，这是最短路径题里常用的技巧，本质上是在一个带有状态维度的图上做 BFS。第二，new_turns只有在方向改变时才加一，这正好匹配连连看的规则。第三，visited 集合里记录了到达某格子的方向和拐弯次数，也就是说同一个格子可能被访问多次，只要方向和拐弯数不同，这是必要的，因为方向会影响后续路径。

3.3 三个必调的剪枝参数

BFS 在 10×12 的棋盘上表现还算可以，但到了 30×40 的大棋盘，就必须做剪枝和优化。

第一个剪枝是“初始方向去重”。起点出队后，如果两个方向是直线相对的（比如上和下），先走哪个都一样，可以在入队时只保留一个方向。这个优化对减少队列长度很有效。

第二个剪枝是“非法终点预判”。在 BFS 开始前，先检查终点四周是否有至少一个空位（或起点本身与终点相邻），否则路径不可能到达。这是一个很便宜的提前退出条件，能省掉大量无效搜索。

第三个剪枝是“按候选路径排序”。在分情况枚举双拐点时，先枚举较短的候选线段。因为短线段更可能不被障碍物阻挡，命中概率更高，平均扫描路径数会下降很多。

下面这张表对比了常用的搜索思路：

3.4 为什么“回溯 + 剪枝”也能用

如果实验要求展示“剪枝算法”，那用回溯法写出“全盘自动求解”是很好的加分点。回溯法的思路是：递归扫描所有可消除对，逐一尝试消除，如果最终能清空棋盘就返回成功。

回溯法里最关键的剪枝是“每次递归先找有且仅有一对可消除的棋子”。如果某一轮只有一对棋子能够相互连通，那么这条分支是唯一确定的，不用尝试其他选择。另一个剪枝是“提前检查剩余棋子是否还有可消除对”，如果当前棋盘上根本不存在任何可消除对，则直接回退，不再扩展子节点。

我实际写代码时，会先实现find_all_pairs得到候选列表，然后对候选列表按“曼哈顿距离”排序，优先消除距离近的。这个排序不影响正确性，但会显著减少回溯深度，尤其是棋盘上一开始就有大量可选消除对的时候。

4. 从控制台到可视化：连连看界面分层与代码落地技巧

很多同学写课设的第一天就打开图形库，结果调了一个星期的坐标映射和事件循环，核心算法一行没写。正确顺序是：先做控制台版，用命令输入坐标验证算法，再包一层可视化界面。这样逻辑和表现分离，出了问题能快速定位到底是算法 bug 还是 UI bug。

4.1 控制台版“最小可运行”架构

控制台版的逻辑层只暴露三个接口：初始化棋盘、尝试消除、判断游戏结束。表现层就是打印棋盘和处理输入。

进入游戏后输入：r1 c1 r2 c2 示例：2 3 2 8 退出：-1 -1 -1 -1

我用一个 while 循环驱动整个游戏流程，代码如下：

while (1) { print_board(board, ROWS, COLS); int r1, c1, r2, c2; printf("> "); scanf("%d %d %d %d", &r1, &c1, &r2, &c2); if (r1 == -1) break; if (is_legal_remove(board, r1, c1, r2, c2)) { board[r1][c1] = 0; board[r2][c2] = 0; printf("消除成功\n"); } else { printf("无法消除\n"); } if (is_game_over(board, ROWS, COLS)) { printf("恭喜通关\n"); break; } }

这个循环非常容易调试。如果发现消除判定有误，直接在控制台里输入坐标，甚至可以写一个自动化脚本去模拟一连串输入，用来做回归测试。界面层的东西全部不碰，这样的分层让核心算法的正确性可以先被验证。

4.2 可视化外壳的常见坑：坐标映射与状态机

当代码迁移到图形界面时，最常见的 bug 是坐标映射。假设每个格子大小是 50×50 像素，点击点(x, y)对应的格子坐标是(y / 50, x / 50)。这里是一个二维数组，第一个下标是行，对应绘图坐标的 y 轴，第二个下标是列，对应 x 轴。

另一个坑是点击状态机。必须区分“当前没有选中任何棋子”“已经选中第一个棋子”“正在播放消除动画”三种状态。如果用一个int selected_r = -1去记录，代码很快就变成一团乱麻。我建议用枚举：

typedef enum { STATE_IDLE, STATE_SELECTED, STATE_ANIMATING } ClickState;

在STATE_SELECTED状态下再次点击同一个格子，应该取消选中；点击另一个格子，则尝试消除。很多初版实现把“取消选中”漏掉，导致用户无法改选。

下面给出逻辑层和表现层的职责划分，这是多层架构的骨架：

4.3 提示功能与全盘扫描的实现

提示功能本质上是一次“找出任意一对可消除棋子”的全盘扫描。在 10×12 的棋盘上，直接双重循环找所有同图案的点对，再调用路径搜索即可。

int find_one_pair(int board[ROWS][COLS], int *r1, int *c1, int *r2, int *c2) { for (int i = 0; i < ROWS; i++) { for (int j = 0; j < COLS; j++) { if (board[i][j] == 0) continue; for (int k = i; k < ROWS; k++) { for (int l = (k == i ? j + 1 : 0); l < COLS; l++) { if (board[k][l] == 0) continue; if (board[i][j] != board[k][l]) continue; if (has_path(board, i, j, k, l)) { *r1 = i; *c1 = j; *r2 = k; *c2 = l; return 1; } } } } } return 0; }

这段代码的关键在for (int l = (k == i ? j + 1 : 0))。它杜绝了“同一对格子被扫描两次”的问题，保证每一对坐标组合最多检查一次。这里的语义是：如果第二层循环还在同一行，就从j+1开始；如果到了下一行，则可以从l=0开始。这个写法能省掉一个重复判断。

4.4 自动洗牌与“无解”检测

当游戏进行到中后期，棋盘上可能会出现没有任何一对可消除的局面。此时需要自动重排剩余棋子。洗牌时不能改变图案数量，所以要先把非空格子的图案收集到临时数组里，打乱顺序后重新填回非空位置。

洗牌完成后，还需要再检查一次是否立即存在可消除对。如果依然不存在，就再洗。为了防止死循环，设定一个最大重试次数，比如 20 次。达到上限后可以直接给用户提示“本局已无解”，这在很多商业连连看里也被称作“死局”。这里的设计逻辑是：洗牌只是“重新排列”，不是“重新生成图案”，因为图案频率表已经定死，重新生成会破坏“每种图案数量偶数”的约束。

5. 最后一关：死局检测、自动求解与性能优化

如果前面的章节只是让你“能玩”，这一章决定实验报告是 80 分还是 95 分。

5.1 死局检测：不能只看剩余棋子数量

游戏结束的条件不是“剩余棋子数为 0”，而是“不存在任何可消除对”。这个检测用第 4 章里的find_one_pair来实现：返回 0 且棋盘上还有非空格子，就是死局。死局时可以做两件事：自动洗牌，或者提示玩家手动洗牌。这里有一个优化点：不要每次消除后都扫描全盘，而是维护一个计数器，当剩余棋子数降到某个阈值（比如 20 个）再扫描，这样能避免每步的无效计算。

5.2 自动求解：用回溯和剪枝跑通全盘

自动求解是“加分项”里最常见的实现。它本质上是对整个消除顺序做一个搜索。因为每一次消除都会改变棋盘，所以必须用带撤销的回溯法。

def solve(board, steps): pairs = find_all_pairs(board) if not pairs and is_empty(board): return steps if not pairs: return None # 剪枝：优先消除“唯一配对”的格子 for r1, c1, r2, c2 in sorted(pairs, key=manhattan_distance): v1, v2 = board[r1][c1], board[r2][c2] board[r1][c1] = board[r2][c2] = 0 result = solve(board, steps + [(r1, c1, r2, c2)]) if result is not None: return result board[r1][c1], board[r2][c2] = v1, v2 return None

在刚才这段代码里，manhattan_distance排序是关键剪枝。距离近的棋子对更容易让棋盘变得“稀疏”，从而给后续消除创造空间。每次递归前先调用is_empty判断提前终止，也避免了不必要的继续搜索。

5.3 棋盘增大时的性能优化策略

如果实验要求支持 30×40 的大棋盘，暴力 BFS 会开始显示卡顿。这时需要做两件事。第一，把“检查两点是否连通”的路径搜索从“每次计算”改为“带缓存记忆化”，用一个哈希表记录已经计算过的点对结果。第二，为每种图案建立“位置索引表”，这样搜索同图案候选点时，不需要遍历整个棋盘。

实测数据表明，10×12 棋盘上的全盘扫描耗时约 5ms，而 30×40 棋盘如果加上位置索引和缓存，扫描时间可以控制在 25ms 以内。这个指标对“提示”按钮来说足够流畅。

5.4 对抗测试：用自动化脚本代替手工点击

最后一个技巧：不要手动点鼠标验证算法。我习惯在逻辑层写一个run_all_tests()函数，里面放几组特殊棋盘：

• 全空棋盘：所有格子为空，任何两点都不应有路径；
• 两个相同图案相邻：必须能直接消除；
• 两个相同图案被一个障碍物隔开：必须被判定为不可消除；
• 两个相同图案位于棋盘外圈对角：验证外圈路径是否生效；
• 只留下一对可消除棋子：验证死局检测能不能正确触发洗牌。

把这些用例写成断言，每次修改完算法后跑一遍，比玩十遍游戏都管用。没有任何一个可靠的连连看实现是完全靠手工点出来的。

本文还有配套的精品资源，点击获取