尧图网站开发 
简介基于MFC的连连看实验项目是一份面向数据结构课程设计与Windows应用开发学习者的完整实践包。项目重点演示二维数组、链表、队列等数据结构在游戏逻辑中的应用并引入广度优先搜索路径匹配与优先队列等进阶用法同时利用MFC的CDC绘图、消息映射、资源加载及文档/视图架构完整实现界面绘制、点击事件、消除动画和状态管理。压缩包内含532个文件既有cpp/h等源码工程文件与vcxproj工程配置也有png/bmp等游戏图片资源、wav音效、ico图标以及可直接运行的exe/dll和PDF/README说明文档整体约287MB目录结构清晰适合用Visual Studio打开调试与二次开发。项目还包含多套背景图、按钮素材可快速体验成品效果。目前已获477人学习适合希望巩固数据结构知识并熟悉MFC桌面开发流程的读者。1. 数据结构实验连连看MFC算法占比远超你想象拿到“数据结构实验连连看MFC”这个题目多数人第一时间会去找精美的位图、打磨按钮样式但实际带过这个实验后会发现MFC在整个工程里只占三成左右剩下七成是棋盘数据结构与路径搜索。连连看看起来是鼠标点两下消一对的小游戏内核却是一道典型的数据结构综合题棋盘用二维数组组织消除判定依赖广度优先搜索开局可用性和残局重排又需要遍历与随机化配合。这篇文章适合正在做课程实验、准备数据结构面试的读者也适合想快速把寻路算法落到界面的MFC初学者。后面的内容不假设你已经熟悉 MFC 文档体系只要看得懂 C 和类就可以顺着代码走完。按数据模型、寻路算法、MFC 交互、增强功能四个层面逐层展开每段代码都能直接进工程验证也会指出那些只跑通一次、换组数据就崩的边界细节。2. 棋盘地图的数据结构选型与初始化2.1 用二维数组模拟棋盘而不是一维链表连连看棋盘是一个矩形网格每个格子要么空、要么放着一种图块。对这个需求二维数组是成本最低、也最容易配合界面刷新的方案Get(r, c)和Set(r, c, v)都是 O(1)View 层重绘时按行列遍历即可。用链表或散列表存储不是不可以但会让“按坐标取牌”“按坐标置空”这两个高频操作变得别扭而且指针操作在实验报告中很难写出亮点。这里有一个关键选型细节棋盘在逻辑上要比可见区域多一圈。也就是说如果界面上显示 10 行 12 列数组要开 12 行 14 列最外圈全部置为EMPTY。原因在于连连看允许路径绕到棋盘外围一块卡在角落的牌也能通过外侧空道和其他同类型牌连通。很多同学直接开[10][12]的数组做搜索结果边缘的牌永远消不掉就是少了这一圈。实际项目中我会把“带外圈棋盘”和“用户可见棋盘”统一成一个模型由同一个类维护。用一维数组模拟二维是为了减少一次内存分配同时保证数据连续调试观察变量时也方便如果追求代码直白用vectorvectorint也没问题几十个格子的规模下性能完全无差别但实验要求“手写数据结构”时一维数组加下标换算反而更好交代。#define EMPTY 0 class CLinkMap { public: CLinkMap() : m_pData(nullptr), m_nRows(0), m_nCols(0) {} ~CLinkMap() { delete[] m_pData; } bool Init(int rows, int cols, int types); int Get(int r, int c) const { return m_pData[r * m_nCols c]; } void Set(int r, int c, int v) { m_pData[r * m_nCols c] v; } int GetRows() const { return m_nRows; } int GetCols() const { return m_nCols; } private: int* m_pData; // 一维数组模拟二维含外圈 int m_nRows; // 含外圈的总行数 int m_nCols; // 含外圈的总列数 };这里的m_nRows、m_nCols都是含外圈的尺寸。比如可见区域 10x12 时Init传入rows12, cols14第 0 行、第rows-1行以及第 0 列、第cols-1列始终是EMPTY不参与初始化配对。这样寻路代码不需要做坐标映射外圈和内部空地统一对待逻辑最干净。2.2 配对、洗牌与可解性检查初始化要做三件事按图案类型成对填充图块、随机洗牌、确认初始局面存在至少一对可消除的图块。成对填充的规则很简单唯一要注意的是图案种类数不能太多否则每种牌数量过少、布局稀疏太少也不行满屏相同类型会让游戏没有过程。常用参数区间见下表。可见区域格子总数图案种类每种图案数量备注8 x 1080810调试阶段推荐跑得快10 x 121201012最常用的作业配置12 x 141681214界面充裕时使用洗牌采用 Fisher-Yates 算法从数组尾部开始逐个与随机位置交换保证每种排列等概率。常见误用是对下标做rand() % n的多次随机交换那样需要大量迭代才能接近均匀分布而且一旦写下while循环容易变成死循环。Fisher-Yates 只需要 n-1 次交换代码短且稳定。洗牌之后必须调用一次可解性检查因为随机排列很容易出现“没有一对牌能通过不超过 2 次转弯连通”的局面。检查逻辑就是双重循环加下文的CanConnect遍历所有非空格子遇到同类型就调用寻路找到一对即可返回true。这个检查最坏情况下要调用几百次寻路但因为 BFS 本身很快整体在毫秒级不会让程序启动变慢。bool CLinkMap::Init(int rows, int cols, int types) { // 可见区域格子数必须是偶数否则无法两两配对 int visible (rows - 2) * (cols - 2); if (visible % 2 ! 0 || types 0 || types visible / 2) return false; m_nRows rows; m_nCols cols; delete[] m_pData; m_pData new int[m_nRows * m_nCols]; // 外圈置 EMPTY内部区域也先清零 memset(m_pData, EMPTY, sizeof(int) * m_nRows * m_nCols); // 收集内部格子坐标按种类成对填充 std::vectorint cells; for (int r 1; r m_nRows - 1; r) for (int c 1; c m_nCols - 1; c) cells.push_back(r * m_nCols c); int totalCells (int)cells.size(); int nPairs totalCells / 2; int base nPairs / types; int extra nPairs % types; int pos 0; for (int t 1; t types; t) { int cnt base (t extra ? 1 : 0); for (int k 0; k cnt; k) { m_pData[cells[pos]] t; m_pData[cells[pos]] t; } } // Fisher-Yates 洗牌只洗内部格子 srand((unsigned)time(nullptr)); for (int i totalCells - 1; i 0; i--) { int j rand() % (i 1); std::swap(m_pData[cells[i]], m_pData[cells[j]]); } // 若初始无解则重新洗牌 while (!HasMovablePair()) { for (int i totalCells - 1; i 0; i--) { int j rand() % (i 1); std::swap(m_pData[cells[i]], m_pData[cells[j]]); } } return true; }参数说明rows和cols传的是含外圈的总行列数所以visible要减 2 再相乘types上限设为可见格子数的一半保证每种图案至少出现一次。memset只适用于EMPTY 0的情况如果换用别的常量表示空白要改成显式循环填充。外圈格子永远不会被洗牌因为在收集cells时已经过滤掉了这就杜绝了“空白格被洗进棋盘内”的低级错误。2.3 数据结构实验中最容易丢分的两个初始化错误第一个错误是忘记外圈。上面提到路径允许从棋盘外围绕行这是连连看规则的一部分不是可选设计。去掉外圈后边缘牌只能走内侧通道很多本来能消的对消不掉可解性检查也失去意义。第二个错误是HasMovablePair只在启动时调用一次游戏中途经过消除后可能出现“全部无解但还有牌”的死局。处理方式有两种点击“洗牌”按钮重排剩余牌或者在每次消除后自动检查然后提示。第五部分会详细讲残局重排这里只需要把HasMovablePair设计成公有方法方便游戏逻辑在任意时刻调用。3. 不超过两次转弯的BFS寻路算法3.1 把“连连看连通”建模成限制转弯次数的搜索寻路是整个实验的核心也是数据结构课最容易考问的部分。规则很简单两个非空格子类型相同并且能找到一条经过它们之间不超过两次转弯的路径路径上所有格子端点除外都必须是空地。这里“空地”包括了棋盘外圈那一层也就是说路径可以走出棋盘边界再从另一个位置绕回来这属于合法路径。把这个规则转换成搜索问题状态就不只是坐标还包括当前行进方向和已经转弯的次数。BFS 在这里比 DFS 合适BFS 会按照转弯次数从少到多扩展状态只要到达终点一定是在合法条件下最先发现的一条DFS 则可能沿着一条长路走到很深处才回溯虽然最终结果一样但状态空间更大代码也更难控制。状态空间定义为(row, col, dir, turns)。dir表示进入当前格子的方向取值 0 上、1 右、2 下、3 左turns取值 0、1、2超过 2 的状态直接丢弃。这样每个格子最多有 4 x 3 12 个状态地图是 12x14 的话总状态不超过 2016BFS 完全不需要额外优化也能在毫秒级返回。3.2 BFS节点结构、剪枝与公共接口节点定义和方向数组如下struct Node { int row, col; // 当前所在格子 int dir; // 进入该格子时的方向 int turns; // 到目前位置的转弯次数 }; const int DR[4] { -1, 0, 1, 0 }; // 上右下左 const int DC[4] { 0, 1, 0, -1 };CanConnect的完整实现需要处理三个前置条件两个格子不能是同一个位置、类型必须相同、不能是空位。然后从起点向四个方向各推一个初始状态因为起点处没有“进入方向”把四个方向的dir分别设为对应值、turns设为 0这样第一步直线移动不产生转弯。扩展时新方向的索引如果和当前dir不同turns加 1超过 2 就剪掉。新位置如果是终点直接返回true否则只有空位才能继续入队。bool CLinkMap::CanConnect(int sr, int sc, int er, int ec) { if (sr er sc ec) return false; if (Get(sr, sc) EMPTY || Get(er, ec) EMPTY) return false; if (Get(sr, sc) ! Get(er, ec)) return false; static bool visited[20][20][4][3]; // 状态表行、列、方向、转弯次数 memset(visited, 0, sizeof(visited)); std::queueNode q; for (int d 0; d 4; d) { q.push({sr, sc, d, 0}); visited[sr][sc][d][0] true; } while (!q.empty()) { Node cur q.front(); q.pop(); for (int nd 0; nd 4; nd) { int nr cur.row DR[nd]; int nc cur.col DC[nd]; int nt cur.turns (nd cur.dir ? 0 : 1); if (nt 2) continue; // 剪枝转弯次数超限 if (nr 0 || nr m_nRows || nc 0 || nc m_nCols) continue; // 越界 if (nr er nc ec) return true; // 到达终点 if (Get(nr, nc) ! EMPTY) continue; // 只能走空格 if (visited[nr][nc][nd][nt]) continue; visited[nr][nc][nd][nt] true; q.push({nr, nc, nd, nt}); } } return false; }逻辑说明visited的四个维度中前两维是地图坐标第三维是进入方向第四维是转弯次数。同一个位置(nr, nc)可能从不同方向、以不同转弯次数到达这些状态各自独立不能互相覆盖否则会少搜路径。这里用静态数组是为了避免在栈上重复分配对常见实验规模足够如果地图超过 18 行 18 列应改用vectorbool动态分配或者把维度提升为全局常量。提示终点判定必须先于空格判断。如果把Get(nr, nc) ! EMPTY写在终点判定之前终点那张牌永远无法成为合法目标函数会对所有输入返回无解。参数说明起点是(sr, sc)终点是(er, ec)两个值都是含外圈的格子坐标调用方需要把屏幕坐标先换算到这个坐标系。状态维度的取值范围见下表写报告时这张表可以直接用。visited 维度含义取值范围第 1 维行坐标0 ~ rows-1第 2 维列坐标0 ~ cols-1第 3 维进入方向0 上 / 1 右 / 2 下 / 3 左第 4 维已转弯次数0 ~ 23.3 路径记录与调试技巧如果实验要求“画出消除路径”需要在 BFS 中记录前驱。一般做法是额外开一个int prev[20][20][4][3]存当前状态由哪个方向转移而来找到终点后从终点往前回溯到起点再把路径按顺序输出。回溯得到的是逆序需要反转后供绘制逻辑使用。调试阶段建议在CanConnect入口和出口加TRACE输出把起点、终点、返回值打出来。这样点击界面时可以在 VS 的输出窗口实时观察每次消除判断是否正确比盯着界面看闪烁直观得多。另外HasMovablePair就是遍历所有可能存在配对的非空格子对对每对调用一次CanConnect找到一个true就返回。把这段遍历单独抽成函数后面做“提示”按钮时可以复用同一个接口区别只是返回第一对可消坐标。4. MFC视图交互与消除刷新流程4.1 在Document里放地图在View里只留绘制状态MFC 的 SDI/MDI 工程默认使用 Document/View 架构这个架构对这个实验非常合适。地图数据放在 Document 类里Init、CanConnect这些方法都通过 Document 暴露给 ViewView 里只记录“当前选中了哪张牌”“鼠标点在哪里”这类界面状态。这样做的核心价值是逻辑与显示分离。后面要扩展“自动求解”只需要操作 Document 里的CLinkMap完全不碰窗口要换成控制台输出测试寻路算法也可以直接构造CLinkMap对象跑函数不用启动界面。有些同学把所有逻辑都塞进 View结果每次重绘都要从窗口句柄开始找数据后期维护非常痛苦。一个典型工程里的类结构是// CLinkGameDoc : public CDocument CLinkMap m_map; // 为便于代码展示设为公有正式工程建议提供 GetMap() 访问器 int m_nRows, m_nCols; // 可见区域行列数初始化时由 m_map 反推 // CLinkGameView : public CView int m_nSelRow, m_nSelCol; // -1 表示未选中 int m_nCellSize; // 每格像素 int m_nMargin; // 棋盘边距初始化时调用m_map.Init(12, 14, 10)其中 12 和 14 是含外圈尺寸对应的可见棋盘为 10 行 12 列。m_nCellSize取值一般在 40 到 60 像素之间太小手指不好点太大窗口装不下。4.2 OnLButtonDown 里的状态机设计鼠标点击处理是整个交互的核心。正确流程分两步第一次点击有牌格子把它记录为选中态界面高亮显示。第二次点击时判断是否同一格、是否同类、是否连通。三者都满足就清空两张牌否则取消选中或切换选中到新格子。判断顺序不能颠倒。“是否同一格”要最先判断防止玩家连续点击同一张牌时产生误消除类型不同时直接把第二次点中的格子变成新的选中项这个细节能明显改善操作手感否则连错一张牌就要重新点两次。void CLinkGameView::OnLButtonDown(UINT nFlags, CPoint point) { CLinkGameDoc* pDoc GetDocument(); // 屏幕坐标 - 含外圈的棋盘坐标 int col (point.x - m_nMargin) / m_nCellSize 1; int row (point.y - m_nMargin) / m_nCellSize 1; if (row 1 || row pDoc-m_map.GetRows() - 1 || col 1 || col pDoc-m_map.GetCols() - 1) { CView::OnLButtonDown(nFlags, point); return; } int type pDoc-m_map.Get(row, col); if (type EMPTY) { m_nSelRow m_nSelCol -1; Invalidate(); CView::OnLButtonDown(nFlags, point); return; } if (m_nSelRow 0) { // 第一次选中 m_nSelRow row; m_nSelCol col; } else { if (row m_nSelRow col m_nSelCol) { // 点同一张牌取消选中 m_nSelRow m_nSelCol -1; } else if (type pDoc-m_map.Get(m_nSelRow, m_nSelCol) pDoc-m_map.CanConnect(row, col, m_nSelRow, m_nSelCol)) { // 连通消掉两张 pDoc-m_map.Set(row, col, EMPTY); pDoc-m_map.Set(m_nSelRow, m_nSelCol, EMPTY); m_nSelRow m_nSelCol -1; } else { // 不连通切换选中到当前点击的牌 m_nSelRow row; m_nSelCol col; } } Invalidate(); CView::OnLButtonDown(nFlags, point); }参数说明point.x - m_nMargin把窗口坐标换算成棋盘内偏移除以m_nCellSize得到列号由于外圈占了一行一列内部第一格的坐标是 1所以结果要加 1。GetRows和GetCols返回含外圈尺寸判断条件里用 ... - 1排除最外圈。首次点击后不立即消除消除动作延迟到第二次点击确认这样状态机只有“未选中”和“已选中”两个显式状态逻辑容易验证。还有一个容易漏掉的细节点击空白格时要把已有选中态清掉。漏掉之后玩家点完空格再点牌会出现第一张选中的牌被莫名替换的怪异现象。Invalidate只负责标记客户区失效真正的重绘在OnDraw里统一完成不要在消息处理里直接拿CDC画图否则消息事件一多就会互相覆盖窗口最小化再恢复后画面也会丢失。4.3 用内存DC重绘避免窗口闪烁消除和选中都需要重绘如果直接用pDC画每次Invalidate都会触发整窗口擦除再重画图块多时能明显看到闪动。标准做法是双缓冲先在内存里创建一块和客户区一样大的位图画好之后一次BitBlt到屏幕。void CLinkGameView::OnDraw(CDC* pDC) { CLinkGameDoc* pDoc GetDocument(); CRect rcClient; GetClientRect(rcClient); CDC memDC; memDC.CreateCompatibleDC(pDC); CBitmap bmp; bmp.CreateCompatibleBitmap(pDC, rcClient.Width(), rcClient.Height()); CBitmap* pOld memDC.SelectObject(bmp); CBrush bg(RGB(235, 235, 235)); memDC.FillRect(rcClient, bg); for (int r 1; r pDoc-m_map.GetRows() - 1; r) { for (int c 1; c pDoc-m_map.GetCols() - 1; c) { CRect rc(m_nMargin (c - 1) * m_nCellSize, m_nMargin (r - 1) * m_nCellSize, m_nMargin c * m_nCellSize, m_nMargin r * m_nCellSize); int type pDoc-m_map.Get(r, c); if (type EMPTY) { memDC.FillSolidRect(rc, RGB(255, 255, 255)); } else { memDC.FillSolidRect(rc, g_colorTable[type % 10]); if (r m_nSelRow c m_nSelCol) { memDC.Draw3dRect(rc, RGB(220, 20, 20), RGB(220, 20, 20)); } } } } pDC-BitBlt(0, 0, rcClient.Width(), rcClient.Height(), memDC, 0, 0, SRCCOPY); memDC.SelectObject(pOld); }逻辑说明内存 DC 和屏幕 DC 兼容绘制规则与数据结构完全对应外圈不画内部格子按Get(r,c)的值上色。g_colorTable是一个静态颜色数组下标取type % 10防止越界换成位图资源时FillSolidRect改成DrawIcon或StretchBlt即可。选中高亮用Draw3dRect画红色边框第一次点击后立刻给出视觉反馈。“数据修改”和“绘制”分成两步是 MFC 程序的基本结构也是答辩时老师经常追问的点。5. 加分项提示、残局洗牌与动画刷新5.1 提示功能就是复用 HasMovablePair把前面遍历配对的计算从bool改成返回坐标提示功能就只剩下一层薄薄的界面逻辑。FindFirstPair本质上就是遍历非空格子并调用CanConnect找到就立刻返回。这个功能看起来不起眼但能体现“算法复用”的意识答辩时比解释一堆界面代码更有说服力。void CLinkGameView::OnBtnHint() { CLinkGameDoc* pDoc GetDocument(); int sr, sc, er, ec; if (pDoc-m_map.FindFirstPair(sr, sc, er, ec)) { m_nSelRow sr; m_nSelCol sc; Invalidate(); } else { AfxMessageBox(_T(当前没有可消除的牌对)); } }实现时注意FindFirstPair返回的是含外圈坐标传入m_nSelRow前不需要换算如果后续要绘制高亮线再把er, ec传给绘制函数。5.2 残局重排保持牌面集合不变死局检查放在每次消除后的逻辑里如果发现“没有可消对但还有牌”就自动重排。重排不能重新生成新牌只能把当前剩余的非空牌打乱位置。常见做法是收集所有非空格子的坐标和牌值对坐标数组做 Fisher-Yates 洗牌再依次填回。循环洗牌直到出现可消对同时设置一个最大重试次数比如 50 次超过后判定为极端死局并弹出结束界面。这个兜底逻辑虽然不常用但能在答辩时证明你处理过状态收敛问题。5.3 计时器驱动的消除动画消除成功后不要立刻Set(...EMPTY)并重绘可以先用SetTimer启动一个 150ms 的计时器让界面短暂停留后再真正置空。这样玩家能看到两张牌被选中、消失的完整过程手感比瞬间消失自然很多。SetTimer(1, 150, nullptr); void CLinkGameView::OnTimer(UINT_PTR nIDEvent) { if (nIDEvent 1) { KillTimer(1); // 在这里执行 Set(...EMPTY) 并 Invalidate() CLinkGameDoc* pDoc GetDocument(); pDoc-m_map.Set(m_nAnimRow, m_nAnimCol, EMPTY); pDoc-m_map.Set(m_nSelRow, m_nSelCol, EMPTY); m_nSelRow m_nSelCol -1; Invalidate(); } CView::OnTimer(nIDEvent); }如果还想做渐隐或滑动效果在OnDraw里增加“动画中”分支根据GetTickCount计算当前帧的透明度或偏移量。最后留一个调试技巧寻路算法出问题时在CanConnect入口用TRACE(_T((%d,%d)-(%d,%d)\n), sr, sc, er, ec)输出再在返回处输出结果配合棋盘矩阵打印所有逻辑问题都能在输出窗口里直接定位。本文还有配套的精品资源点击获取 
简介基于MFC的连连看实验项目是一份面向数据结构课程设计与Windows应用开发学习者的完整实践包。项目重点演示二维数组、链表、队列等数据结构在游戏逻辑中的应用并引入广度优先搜索路径匹配与优先队列等进阶用法同时利用MFC的CDC绘图、消息映射、资源加载及文档/视图架构完整实现界面绘制、点击事件、消除动画和状态管理。压缩包内含532个文件既有cpp/h等源码工程文件与vcxproj工程配置也有png/bmp等游戏图片资源、wav音效、ico图标以及可直接运行的exe/dll和PDF/README说明文档整体约287MB目录结构清晰适合用Visual Studio打开调试与二次开发。项目还包含多套背景图、按钮素材可快速体验成品效果。目前已获477人学习适合希望巩固数据结构知识并熟悉MFC桌面开发流程的读者。1. 数据结构实验连连看MFC算法占比远超你想象拿到“数据结构实验连连看MFC”这个题目多数人第一时间会去找精美的位图、打磨按钮样式但实际带过这个实验后会发现MFC在整个工程里只占三成左右剩下七成是棋盘数据结构与路径搜索。连连看看起来是鼠标点两下消一对的小游戏内核却是一道典型的数据结构综合题棋盘用二维数组组织消除判定依赖广度优先搜索开局可用性和残局重排又需要遍历与随机化配合。这篇文章适合正在做课程实验、准备数据结构面试的读者也适合想快速把寻路算法落到界面的MFC初学者。后面的内容不假设你已经熟悉 MFC 文档体系只要看得懂 C 和类就可以顺着代码走完。按数据模型、寻路算法、MFC 交互、增强功能四个层面逐层展开每段代码都能直接进工程验证也会指出那些只跑通一次、换组数据就崩的边界细节。2. 棋盘地图的数据结构选型与初始化2.1 用二维数组模拟棋盘而不是一维链表连连看棋盘是一个矩形网格每个格子要么空、要么放着一种图块。对这个需求二维数组是成本最低、也最容易配合界面刷新的方案Get(r, c)和Set(r, c, v)都是 O(1)View 层重绘时按行列遍历即可。用链表或散列表存储不是不可以但会让“按坐标取牌”“按坐标置空”这两个高频操作变得别扭而且指针操作在实验报告中很难写出亮点。这里有一个关键选型细节棋盘在逻辑上要比可见区域多一圈。也就是说如果界面上显示 10 行 12 列数组要开 12 行 14 列最外圈全部置为EMPTY。原因在于连连看允许路径绕到棋盘外围一块卡在角落的牌也能通过外侧空道和其他同类型牌连通。很多同学直接开[10][12]的数组做搜索结果边缘的牌永远消不掉就是少了这一圈。实际项目中我会把“带外圈棋盘”和“用户可见棋盘”统一成一个模型由同一个类维护。用一维数组模拟二维是为了减少一次内存分配同时保证数据连续调试观察变量时也方便如果追求代码直白用vectorvectorint也没问题几十个格子的规模下性能完全无差别但实验要求“手写数据结构”时一维数组加下标换算反而更好交代。#define EMPTY 0 class CLinkMap { public: CLinkMap() : m_pData(nullptr), m_nRows(0), m_nCols(0) {} ~CLinkMap() { delete[] m_pData; } bool Init(int rows, int cols, int types); int Get(int r, int c) const { return m_pData[r * m_nCols c]; } void Set(int r, int c, int v) { m_pData[r * m_nCols c] v; } int GetRows() const { return m_nRows; } int GetCols() const { return m_nCols; } private: int* m_pData; // 一维数组模拟二维含外圈 int m_nRows; // 含外圈的总行数 int m_nCols; // 含外圈的总列数 };这里的m_nRows、m_nCols都是含外圈的尺寸。比如可见区域 10x12 时Init传入rows12, cols14第 0 行、第rows-1行以及第 0 列、第cols-1列始终是EMPTY不参与初始化配对。这样寻路代码不需要做坐标映射外圈和内部空地统一对待逻辑最干净。2.2 配对、洗牌与可解性检查初始化要做三件事按图案类型成对填充图块、随机洗牌、确认初始局面存在至少一对可消除的图块。成对填充的规则很简单唯一要注意的是图案种类数不能太多否则每种牌数量过少、布局稀疏太少也不行满屏相同类型会让游戏没有过程。常用参数区间见下表。可见区域格子总数图案种类每种图案数量备注8 x 1080810调试阶段推荐跑得快10 x 121201012最常用的作业配置12 x 141681214界面充裕时使用洗牌采用 Fisher-Yates 算法从数组尾部开始逐个与随机位置交换保证每种排列等概率。常见误用是对下标做rand() % n的多次随机交换那样需要大量迭代才能接近均匀分布而且一旦写下while循环容易变成死循环。Fisher-Yates 只需要 n-1 次交换代码短且稳定。洗牌之后必须调用一次可解性检查因为随机排列很容易出现“没有一对牌能通过不超过 2 次转弯连通”的局面。检查逻辑就是双重循环加下文的CanConnect遍历所有非空格子遇到同类型就调用寻路找到一对即可返回true。这个检查最坏情况下要调用几百次寻路但因为 BFS 本身很快整体在毫秒级不会让程序启动变慢。bool CLinkMap::Init(int rows, int cols, int types) { // 可见区域格子数必须是偶数否则无法两两配对 int visible (rows - 2) * (cols - 2); if (visible % 2 ! 0 || types 0 || types visible / 2) return false; m_nRows rows; m_nCols cols; delete[] m_pData; m_pData new int[m_nRows * m_nCols]; // 外圈置 EMPTY内部区域也先清零 memset(m_pData, EMPTY, sizeof(int) * m_nRows * m_nCols); // 收集内部格子坐标按种类成对填充 std::vectorint cells; for (int r 1; r m_nRows - 1; r) for (int c 1; c m_nCols - 1; c) cells.push_back(r * m_nCols c); int totalCells (int)cells.size(); int nPairs totalCells / 2; int base nPairs / types; int extra nPairs % types; int pos 0; for (int t 1; t types; t) { int cnt base (t extra ? 1 : 0); for (int k 0; k cnt; k) { m_pData[cells[pos]] t; m_pData[cells[pos]] t; } } // Fisher-Yates 洗牌只洗内部格子 srand((unsigned)time(nullptr)); for (int i totalCells - 1; i 0; i--) { int j rand() % (i 1); std::swap(m_pData[cells[i]], m_pData[cells[j]]); } // 若初始无解则重新洗牌 while (!HasMovablePair()) { for (int i totalCells - 1; i 0; i--) { int j rand() % (i 1); std::swap(m_pData[cells[i]], m_pData[cells[j]]); } } return true; }参数说明rows和cols传的是含外圈的总行列数所以visible要减 2 再相乘types上限设为可见格子数的一半保证每种图案至少出现一次。memset只适用于EMPTY 0的情况如果换用别的常量表示空白要改成显式循环填充。外圈格子永远不会被洗牌因为在收集cells时已经过滤掉了这就杜绝了“空白格被洗进棋盘内”的低级错误。2.3 数据结构实验中最容易丢分的两个初始化错误第一个错误是忘记外圈。上面提到路径允许从棋盘外围绕行这是连连看规则的一部分不是可选设计。去掉外圈后边缘牌只能走内侧通道很多本来能消的对消不掉可解性检查也失去意义。第二个错误是HasMovablePair只在启动时调用一次游戏中途经过消除后可能出现“全部无解但还有牌”的死局。处理方式有两种点击“洗牌”按钮重排剩余牌或者在每次消除后自动检查然后提示。第五部分会详细讲残局重排这里只需要把HasMovablePair设计成公有方法方便游戏逻辑在任意时刻调用。3. 不超过两次转弯的BFS寻路算法3.1 把“连连看连通”建模成限制转弯次数的搜索寻路是整个实验的核心也是数据结构课最容易考问的部分。规则很简单两个非空格子类型相同并且能找到一条经过它们之间不超过两次转弯的路径路径上所有格子端点除外都必须是空地。这里“空地”包括了棋盘外圈那一层也就是说路径可以走出棋盘边界再从另一个位置绕回来这属于合法路径。把这个规则转换成搜索问题状态就不只是坐标还包括当前行进方向和已经转弯的次数。BFS 在这里比 DFS 合适BFS 会按照转弯次数从少到多扩展状态只要到达终点一定是在合法条件下最先发现的一条DFS 则可能沿着一条长路走到很深处才回溯虽然最终结果一样但状态空间更大代码也更难控制。状态空间定义为(row, col, dir, turns)。dir表示进入当前格子的方向取值 0 上、1 右、2 下、3 左turns取值 0、1、2超过 2 的状态直接丢弃。这样每个格子最多有 4 x 3 12 个状态地图是 12x14 的话总状态不超过 2016BFS 完全不需要额外优化也能在毫秒级返回。3.2 BFS节点结构、剪枝与公共接口节点定义和方向数组如下struct Node { int row, col; // 当前所在格子 int dir; // 进入该格子时的方向 int turns; // 到目前位置的转弯次数 }; const int DR[4] { -1, 0, 1, 0 }; // 上右下左 const int DC[4] { 0, 1, 0, -1 };CanConnect的完整实现需要处理三个前置条件两个格子不能是同一个位置、类型必须相同、不能是空位。然后从起点向四个方向各推一个初始状态因为起点处没有“进入方向”把四个方向的dir分别设为对应值、turns设为 0这样第一步直线移动不产生转弯。扩展时新方向的索引如果和当前dir不同turns加 1超过 2 就剪掉。新位置如果是终点直接返回true否则只有空位才能继续入队。bool CLinkMap::CanConnect(int sr, int sc, int er, int ec) { if (sr er sc ec) return false; if (Get(sr, sc) EMPTY || Get(er, ec) EMPTY) return false; if (Get(sr, sc) ! Get(er, ec)) return false; static bool visited[20][20][4][3]; // 状态表行、列、方向、转弯次数 memset(visited, 0, sizeof(visited)); std::queueNode q; for (int d 0; d 4; d) { q.push({sr, sc, d, 0}); visited[sr][sc][d][0] true; } while (!q.empty()) { Node cur q.front(); q.pop(); for (int nd 0; nd 4; nd) { int nr cur.row DR[nd]; int nc cur.col DC[nd]; int nt cur.turns (nd cur.dir ? 0 : 1); if (nt 2) continue; // 剪枝转弯次数超限 if (nr 0 || nr m_nRows || nc 0 || nc m_nCols) continue; // 越界 if (nr er nc ec) return true; // 到达终点 if (Get(nr, nc) ! EMPTY) continue; // 只能走空格 if (visited[nr][nc][nd][nt]) continue; visited[nr][nc][nd][nt] true; q.push({nr, nc, nd, nt}); } } return false; }逻辑说明visited的四个维度中前两维是地图坐标第三维是进入方向第四维是转弯次数。同一个位置(nr, nc)可能从不同方向、以不同转弯次数到达这些状态各自独立不能互相覆盖否则会少搜路径。这里用静态数组是为了避免在栈上重复分配对常见实验规模足够如果地图超过 18 行 18 列应改用vectorbool动态分配或者把维度提升为全局常量。提示终点判定必须先于空格判断。如果把Get(nr, nc) ! EMPTY写在终点判定之前终点那张牌永远无法成为合法目标函数会对所有输入返回无解。参数说明起点是(sr, sc)终点是(er, ec)两个值都是含外圈的格子坐标调用方需要把屏幕坐标先换算到这个坐标系。状态维度的取值范围见下表写报告时这张表可以直接用。visited 维度含义取值范围第 1 维行坐标0 ~ rows-1第 2 维列坐标0 ~ cols-1第 3 维进入方向0 上 / 1 右 / 2 下 / 3 左第 4 维已转弯次数0 ~ 23.3 路径记录与调试技巧如果实验要求“画出消除路径”需要在 BFS 中记录前驱。一般做法是额外开一个int prev[20][20][4][3]存当前状态由哪个方向转移而来找到终点后从终点往前回溯到起点再把路径按顺序输出。回溯得到的是逆序需要反转后供绘制逻辑使用。调试阶段建议在CanConnect入口和出口加TRACE输出把起点、终点、返回值打出来。这样点击界面时可以在 VS 的输出窗口实时观察每次消除判断是否正确比盯着界面看闪烁直观得多。另外HasMovablePair就是遍历所有可能存在配对的非空格子对对每对调用一次CanConnect找到一个true就返回。把这段遍历单独抽成函数后面做“提示”按钮时可以复用同一个接口区别只是返回第一对可消坐标。4. MFC视图交互与消除刷新流程4.1 在Document里放地图在View里只留绘制状态MFC 的 SDI/MDI 工程默认使用 Document/View 架构这个架构对这个实验非常合适。地图数据放在 Document 类里Init、CanConnect这些方法都通过 Document 暴露给 ViewView 里只记录“当前选中了哪张牌”“鼠标点在哪里”这类界面状态。这样做的核心价值是逻辑与显示分离。后面要扩展“自动求解”只需要操作 Document 里的CLinkMap完全不碰窗口要换成控制台输出测试寻路算法也可以直接构造CLinkMap对象跑函数不用启动界面。有些同学把所有逻辑都塞进 View结果每次重绘都要从窗口句柄开始找数据后期维护非常痛苦。一个典型工程里的类结构是// CLinkGameDoc : public CDocument CLinkMap m_map; // 为便于代码展示设为公有正式工程建议提供 GetMap() 访问器 int m_nRows, m_nCols; // 可见区域行列数初始化时由 m_map 反推 // CLinkGameView : public CView int m_nSelRow, m_nSelCol; // -1 表示未选中 int m_nCellSize; // 每格像素 int m_nMargin; // 棋盘边距初始化时调用m_map.Init(12, 14, 10)其中 12 和 14 是含外圈尺寸对应的可见棋盘为 10 行 12 列。m_nCellSize取值一般在 40 到 60 像素之间太小手指不好点太大窗口装不下。4.2 OnLButtonDown 里的状态机设计鼠标点击处理是整个交互的核心。正确流程分两步第一次点击有牌格子把它记录为选中态界面高亮显示。第二次点击时判断是否同一格、是否同类、是否连通。三者都满足就清空两张牌否则取消选中或切换选中到新格子。判断顺序不能颠倒。“是否同一格”要最先判断防止玩家连续点击同一张牌时产生误消除类型不同时直接把第二次点中的格子变成新的选中项这个细节能明显改善操作手感否则连错一张牌就要重新点两次。void CLinkGameView::OnLButtonDown(UINT nFlags, CPoint point) { CLinkGameDoc* pDoc GetDocument(); // 屏幕坐标 - 含外圈的棋盘坐标 int col (point.x - m_nMargin) / m_nCellSize 1; int row (point.y - m_nMargin) / m_nCellSize 1; if (row 1 || row pDoc-m_map.GetRows() - 1 || col 1 || col pDoc-m_map.GetCols() - 1) { CView::OnLButtonDown(nFlags, point); return; } int type pDoc-m_map.Get(row, col); if (type EMPTY) { m_nSelRow m_nSelCol -1; Invalidate(); CView::OnLButtonDown(nFlags, point); return; } if (m_nSelRow 0) { // 第一次选中 m_nSelRow row; m_nSelCol col; } else { if (row m_nSelRow col m_nSelCol) { // 点同一张牌取消选中 m_nSelRow m_nSelCol -1; } else if (type pDoc-m_map.Get(m_nSelRow, m_nSelCol) pDoc-m_map.CanConnect(row, col, m_nSelRow, m_nSelCol)) { // 连通消掉两张 pDoc-m_map.Set(row, col, EMPTY); pDoc-m_map.Set(m_nSelRow, m_nSelCol, EMPTY); m_nSelRow m_nSelCol -1; } else { // 不连通切换选中到当前点击的牌 m_nSelRow row; m_nSelCol col; } } Invalidate(); CView::OnLButtonDown(nFlags, point); }参数说明point.x - m_nMargin把窗口坐标换算成棋盘内偏移除以m_nCellSize得到列号由于外圈占了一行一列内部第一格的坐标是 1所以结果要加 1。GetRows和GetCols返回含外圈尺寸判断条件里用 ... - 1排除最外圈。首次点击后不立即消除消除动作延迟到第二次点击确认这样状态机只有“未选中”和“已选中”两个显式状态逻辑容易验证。还有一个容易漏掉的细节点击空白格时要把已有选中态清掉。漏掉之后玩家点完空格再点牌会出现第一张选中的牌被莫名替换的怪异现象。Invalidate只负责标记客户区失效真正的重绘在OnDraw里统一完成不要在消息处理里直接拿CDC画图否则消息事件一多就会互相覆盖窗口最小化再恢复后画面也会丢失。4.3 用内存DC重绘避免窗口闪烁消除和选中都需要重绘如果直接用pDC画每次Invalidate都会触发整窗口擦除再重画图块多时能明显看到闪动。标准做法是双缓冲先在内存里创建一块和客户区一样大的位图画好之后一次BitBlt到屏幕。void CLinkGameView::OnDraw(CDC* pDC) { CLinkGameDoc* pDoc GetDocument(); CRect rcClient; GetClientRect(rcClient); CDC memDC; memDC.CreateCompatibleDC(pDC); CBitmap bmp; bmp.CreateCompatibleBitmap(pDC, rcClient.Width(), rcClient.Height()); CBitmap* pOld memDC.SelectObject(bmp); CBrush bg(RGB(235, 235, 235)); memDC.FillRect(rcClient, bg); for (int r 1; r pDoc-m_map.GetRows() - 1; r) { for (int c 1; c pDoc-m_map.GetCols() - 1; c) { CRect rc(m_nMargin (c - 1) * m_nCellSize, m_nMargin (r - 1) * m_nCellSize, m_nMargin c * m_nCellSize, m_nMargin r * m_nCellSize); int type pDoc-m_map.Get(r, c); if (type EMPTY) { memDC.FillSolidRect(rc, RGB(255, 255, 255)); } else { memDC.FillSolidRect(rc, g_colorTable[type % 10]); if (r m_nSelRow c m_nSelCol) { memDC.Draw3dRect(rc, RGB(220, 20, 20), RGB(220, 20, 20)); } } } } pDC-BitBlt(0, 0, rcClient.Width(), rcClient.Height(), memDC, 0, 0, SRCCOPY); memDC.SelectObject(pOld); }逻辑说明内存 DC 和屏幕 DC 兼容绘制规则与数据结构完全对应外圈不画内部格子按Get(r,c)的值上色。g_colorTable是一个静态颜色数组下标取type % 10防止越界换成位图资源时FillSolidRect改成DrawIcon或StretchBlt即可。选中高亮用Draw3dRect画红色边框第一次点击后立刻给出视觉反馈。“数据修改”和“绘制”分成两步是 MFC 程序的基本结构也是答辩时老师经常追问的点。5. 加分项提示、残局洗牌与动画刷新5.1 提示功能就是复用 HasMovablePair把前面遍历配对的计算从bool改成返回坐标提示功能就只剩下一层薄薄的界面逻辑。FindFirstPair本质上就是遍历非空格子并调用CanConnect找到就立刻返回。这个功能看起来不起眼但能体现“算法复用”的意识答辩时比解释一堆界面代码更有说服力。void CLinkGameView::OnBtnHint() { CLinkGameDoc* pDoc GetDocument(); int sr, sc, er, ec; if (pDoc-m_map.FindFirstPair(sr, sc, er, ec)) { m_nSelRow sr; m_nSelCol sc; Invalidate(); } else { AfxMessageBox(_T(当前没有可消除的牌对)); } }实现时注意FindFirstPair返回的是含外圈坐标传入m_nSelRow前不需要换算如果后续要绘制高亮线再把er, ec传给绘制函数。5.2 残局重排保持牌面集合不变死局检查放在每次消除后的逻辑里如果发现“没有可消对但还有牌”就自动重排。重排不能重新生成新牌只能把当前剩余的非空牌打乱位置。常见做法是收集所有非空格子的坐标和牌值对坐标数组做 Fisher-Yates 洗牌再依次填回。循环洗牌直到出现可消对同时设置一个最大重试次数比如 50 次超过后判定为极端死局并弹出结束界面。这个兜底逻辑虽然不常用但能在答辩时证明你处理过状态收敛问题。5.3 计时器驱动的消除动画消除成功后不要立刻Set(...EMPTY)并重绘可以先用SetTimer启动一个 150ms 的计时器让界面短暂停留后再真正置空。这样玩家能看到两张牌被选中、消失的完整过程手感比瞬间消失自然很多。SetTimer(1, 150, nullptr); void CLinkGameView::OnTimer(UINT_PTR nIDEvent) { if (nIDEvent 1) { KillTimer(1); // 在这里执行 Set(...EMPTY) 并 Invalidate() CLinkGameDoc* pDoc GetDocument(); pDoc-m_map.Set(m_nAnimRow, m_nAnimCol, EMPTY); pDoc-m_map.Set(m_nSelRow, m_nSelCol, EMPTY); m_nSelRow m_nSelCol -1; Invalidate(); } CView::OnTimer(nIDEvent); }如果还想做渐隐或滑动效果在OnDraw里增加“动画中”分支根据GetTickCount计算当前帧的透明度或偏移量。最后留一个调试技巧寻路算法出问题时在CanConnect入口用TRACE(_T((%d,%d)-(%d,%d)\n), sr, sc, er, ec)输出再在返回处输出结果配合棋盘矩阵打印所有逻辑问题都能在输出窗口里直接定位。本文还有配套的精品资源点击获取