1. 项目概述与核心价值最近在准备华为OD机试的同学们应该都感受到了B卷题目那种“接地气”又“暗藏玄机”的风格。它不像A卷那样直来直去考基础语法也不像C卷那样可能涉及更复杂的系统设计B卷的题目往往是一个个具体的、生活化的场景但背后考察的却是扎实的数据结构应用、清晰的逻辑思维和严谨的编码习惯。今天要拆解的这道“连连看游戏”就是B卷中非常经典的一道题。它听起来像是个小游戏似乎不难但真要在有限的考试时间内从零开始设计算法、处理边界、写出bug-free的代码对很多同学来说是个不小的挑战。这道题的核心价值在哪里首先它完美覆盖了B卷的考察重点二维矩阵的处理、搜索算法特别是BFS/DFS、路径判断与连通性分析。这些都是软件开发中处理地图、图像、网格化数据的基础能力。其次“连连看”的规则本身两点直线连接且拐点不超过两个是一个绝佳的算法抽象案例能很好地区分候选人是否具备将实际问题转化为计算模型的能力。最后用C实现还额外考察了对STL容器如vector,queue、内存管理以及代码效率的掌控力。可以说吃透这道题不仅是为了通过机试更是对自身算法与工程能力的一次扎实练兵。接下来我就结合自己多年的开发经验和面试官视角带你层层剥开这道题从思路到实现从踩坑到优化给你一份能直接“抄作业”的实战指南。2. 问题解析与抽象建模拿到题目第一步不是急着写代码而是彻底理解问题并把它翻译成计算机能处理的语言。我们先把“连连看游戏”的规则用技术语言重新定义一遍。2.1 规则的技术化定义题目通常会提供一个N x M的整数矩阵代表游戏棋盘。每个格子上的数字代表一种图案0通常表示空白格。我们需要判断用户选定的两个位置(x1, y1)和(x2, y2)上的图案是否相同且非空并且能否在“三线以内”的路径上相连。这里的“三线以内”就是连连看经典规则连接路径最多只能有2个拐点即路径由至多3条直线段组成。这可以转化为一个路径搜索问题在矩阵中寻找一条从起点到终点的路径该路径需满足除起点和终点外路径上所有经过的格子必须是空白格值为0。路径的“方向改变次数”不超过2次即拐点 ≤ 2。2.2 核心难点与思路选择难点显而易见如何高效地搜索这种带有“拐点限制”的路径暴力DFS遍历所有路径显然不可取因为棋盘可能不小。这里的关键洞察是由于拐点限制很严≤2可能的路径形态其实非常有限。总共只有几种情况0拐点直线起点和终点在同一行或同一列且中间全是空白。1个拐点折线路径像一个“L”形。拐点C必须与起点同行且与终点同列或者与起点同列且与终点同行并且两段直线路径都畅通。2个拐点“Z”形或“U”形路径可以想象成从起点水平走再垂直走再水平走到终点或者先垂直再水平再垂直。这需要两个拐点C1和C2。基于这个观察我们有两种主流实现思路思路一分类讨论穷举法。直接按照0、1、2个拐点的三种情况去检查是否存在满足条件的拐点。这种方法代码直观容易理解在棋盘不大时效率没问题非常适合机试这种强调正确率和速度的场景。思路二广度优先搜索BFS状态扩展法。将(坐标x, 坐标y, 当前方向, 已用拐点数)作为一个状态进行BFS。这种方法更通用能处理更复杂的路径寻找问题但状态设计和实现稍复杂。对于华为OD机试我强烈推荐思路一。理由很简单机试时间紧题目通常不会把矩阵维度出得巨大比如超过50x50分类讨论法时间复杂度是O(N*M)完全够用且代码结构清晰不易出错。BFS法虽然优雅但实现细节多在紧张环境下更容易写出bug。我们追求的是在有限时间内稳定拿分。所以下文将围绕分类讨论穷举法展开。注意有些变体题目可能要求找出“拐点数最少的路径”而不仅仅是判断能否连接。这种情况下BFS状态扩展法是更优解。但根据历年真题风格“连连看”通常只要求判断是否可连因此分类讨论法是最佳实践。3. 算法设计与实现详解我们确定了使用分类讨论法。接下来设计核心的辅助函数和主判断逻辑。3.1 核心辅助函数设计我们需要一个关键的辅助函数checkLine(x1, y1, x2, y2)。它的功能是判断两点是否在同一直线同行或同列上且中间所有格子不包括起点终点是否均为空白值为0。这个函数是后续所有判断的基础。实现时要注意边界检查以及“中间”格子的遍历方向。/** * 检查从(x1,y1)到(x2,y2)的直线路径是否畅通两点必须在同一行或同一列。 * param board 游戏棋盘 * param x1, y1 起点坐标 * param x2, y2 终点坐标 * return true 如果路径畅通且两点非空白否则false */ bool checkLine(const vectorvectorint board, int x1, int y1, int x2, int y2) { // 基础检查两点是否重合是否值相等且非零 if (x1 x2 y1 y2) return false; if (board[x1][y1] ! board[x2][y2] || board[x1][y1] 0) return false; // 检查是否在同一行 if (x1 x2) { int startY min(y1, y2); int endY max(y1, y2); for (int y startY 1; y endY; y) { if (board[x1][y] ! 0) { // 中间有非空块阻挡 return false; } } return true; // 直线畅通 } // 检查是否在同一列 if (y1 y2) { int startX min(x1, x2); int endX max(x1, x2); for (int x startX 1; x endX; x) { if (board[x][y1] ! 0) { return false; } } return true; } // 既不同行也不同列不是直线 return false; }3.2 主逻辑三类路径的判定有了checkLine我们就可以像搭积木一样构建三种情况的判断。情况10拐点直线连接这是最简单的情况直接调用checkLine即可。情况21个拐点L形连接假设拐点为C(cx, cy)。那么路径是A - C - B。要满足A和C在同一直线且路径畅通 (checkLine(A, C)为真)。C和B在同一直线且路径畅通 (checkLine(C, B)为真)。点C必须是空白格因为路径要经过它。但注意在checkLine函数中我们检查的是A到C和C到B的线段C作为这两条线段的端点在checkLine的逻辑里是不检查其是否为空的因为检查的是两点之间的格子。然而在拐点处C本身必须是空白的否则无法“转弯”。这里是一个易错点我们需要额外确保board[cx][cy] 0。那么这样的拐点C可能在哪里它必须同时与A同行或同列且与B同列或同行。因此可能的拐点只有两个(x1, y2)和(x2, y1)。我们只需要检查这两个点是否满足上述三个条件即可。情况32个拐点Z形或U形连接这是最复杂的情况。路径形如A - C1 - C2 - B。我们可以将其理解为存在一个空白点C1使得A和C1直线连通同时存在一个空白点C2使得C1和C2直线连通并且C2和B直线连通。且C1和C2都是空白。但更高效的思考方式是两个拐点意味着路径由三段直线组成。我们可以想象从A点水平发射一条线从B点也水平发射一条线或者都垂直发射如果这两条线能在某个空白列或行上通过一条垂直线或水平线连接起来且所有途径格子为空则连通。一种经典的实现方法是“扩展扫描法”将起点A向上、下、左、右四个方向直线延伸直到遇到障碍物或边界记录下所有能直达的空白格位置这些位置可以作为潜在的C1。同样将终点B向四个方向直线延伸记录所有能直达的空白格位置作为潜在的C2。检查是否存在一对(C1, C2)满足C1和C2在同一行或同一列并且它们之间的直线路径是畅通的。如果存在那么A-C1-C2-B就是一条有效路径。这种方法在实现上比盲目遍历所有C1、C2组合更高效。但对于机试我们也可以采用一种更“暴力”但易于编码和理解的方法遍历所有可能的空白格作为C1然后检查是否存在一个C2使得A-C1连通、C1-C2连通、C2-B连通。由于有拐点限制C1和C2的连通也必须是直线即0拐点。所以这等价于寻找一个空白格C1它分别与A和某个空白格C2直线连通而C2又与B直线连通。这听起来像是两层循环但我们可以优化一旦找到与A直线连通的空白格C1我们只需要从C1出发再向四个方向直线延伸寻找能与B直线连通的空白格C2即可。3.3 代码整合与实现将上述思路整合以下是完整的C实现示例。代码包含了详细的注释并遵循了清晰的模块化设计。#include iostream #include vector #include queue // 如果后续想改用BFS可引入 using namespace std; class LinkGameSolver { private: vectorvectorint board; int n, m; // 棋盘行数、列数 // 判断坐标是否在棋盘内 bool inBounds(int x, int y) { return x 0 x n y 0 y m; } // 核心辅助函数检查直线连通性 bool checkLine(int x1, int y1, int x2, int y2) { if (!inBounds(x1, y1) || !inBounds(x2, y2)) return false; if (board[x1][y1] ! board[x2][y2] || board[x1][y1] 0) return false; if (x1 x2 y1 y2) return false; // 同一行 if (x1 x2) { int startY min(y1, y2); int endY max(y1, y2); for (int y startY 1; y endY; y) { if (board[x1][y] ! 0) return false; } return true; } // 同一列 if (y1 y2) { int startX min(x1, x2); int endX max(x1, x2); for (int x startX 1; x endX; x) { if (board[x][y1] ! 0) return false; } return true; } return false; } // 检查一个拐点的情况 bool checkOneCorner(int x1, int y1, int x2, int y2) { // 可能的拐点只有两个 (x1, y2) 和 (x2, y1) // 检查拐点C1: (x1, y2) if (inBounds(x1, y2) board[x1][y2] 0) { // A到C1需要直线连通且C1到B需要直线连通 // 注意A到C1是(x1,y1)-(x1,y2)是水平线C1到B是(x1,y2)-(x2,y2)是垂直线 // 但我们的checkLine函数已经包含了“中间全为空”的判断所以可以直接用。 // 关键点checkLine不检查端点是否为空所以这里需要额外确保C1为空前面已判断。 if (checkLine(x1, y1, x1, y2) checkLine(x1, y2, x2, y2)) { return true; } } // 检查拐点C2: (x2, y1) if (inBounds(x2, y1) board[x2][y1] 0) { if (checkLine(x1, y1, x2, y1) checkLine(x2, y1, x2, y2)) { return true; } } return false; } // 检查两个拐点的情况 - 扩展扫描法高效版 bool checkTwoCorners(int x1, int y1, int x2, int y2) { // 从起点A向四个方向扩展记录能直线到达的所有空白格作为C1候选 vectorpairint, int reachableFromA; // 向上 for (int x x1 - 1; x 0; --x) { if (board[x][y1] ! 0) break; // 遇到障碍停止 reachableFromA.emplace_back(x, y1); } // 向下 for (int x x1 1; x n; x) { if (board[x][y1] ! 0) break; reachableFromA.emplace_back(x, y1); } // 向左 for (int y y1 - 1; y 0; --y) { if (board[x1][y] ! 0) break; reachableFromA.emplace_back(x1, y); } // 向右 for (int y y1 1; y m; y) { if (board[x1][y] ! 0) break; reachableFromA.emplace_back(x1, y); } // 从终点B向四个方向扩展记录能直线到达的所有空白格作为C2候选 vectorpairint, int reachableFromB; // 向上 for (int x x2 - 1; x 0; --x) { if (board[x][y2] ! 0) break; reachableFromB.emplace_back(x, y2); } // 向下 for (int x x2 1; x n; x) { if (board[x][y2] ! 0) break; reachableFromB.emplace_back(x, y2); } // 向左 for (int y y2 - 1; y 0; --y) { if (board[x2][y] ! 0) break; reachableFromB.emplace_back(x2, y); } // 向右 for (int y y2 1; y m; y) { if (board[x2][y] ! 0) break; reachableFromB.emplace_back(x2, y); } // 遍历所有C1和C2的组合检查C1和C2是否直线连通 for (const auto c1 : reachableFromA) { for (const auto c2 : reachableFromB) { // 如果C1和C2在同一行或同一列且它们之间直线畅通则找到路径 if ((c1.first c2.first || c1.second c2.second)) { // 注意c1和c2都是空白格且与A/B直线连通的条件已由扩展过程保证。 // 现在只需检查c1到c2的直线是否畅通。 if (checkLine(c1.first, c1.second, c2.first, c2.second)) { return true; } } } } return false; } public: LinkGameSolver(const vectorvectorint b) : board(b) { n board.size(); if (n 0) m board[0].size(); else m 0; } // 主接口判断两点是否可连 bool canLink(int x1, int y1, int x2, int y2) { // 0. 基础校验 if (!inBounds(x1, y1) || !inBounds(x2, y2)) return false; if (board[x1][y1] ! board[x2][y2] || board[x1][y1] 0) return false; // 1. 检查0拐点直线 if (checkLine(x1, y1, x2, y2)) { return true; } // 2. 检查1个拐点 if (checkOneCorner(x1, y1, x2, y2)) { return true; } // 3. 检查2个拐点 if (checkTwoCorners(x1, y1, x2, y2)) { return true; } return false; } }; // 示例使用 int main() { // 示例棋盘0表示空白 vectorvectorint board { {1, 0, 0, 2}, {0, 3, 0, 0}, {0, 0, 4, 0}, {5, 0, 0, 1} }; LinkGameSolver solver(board); // 测试点 (0,0) 的1 和 (3,3) 的1 能否相连 if (solver.canLink(0, 0, 3, 3)) { cout 可以连接 endl; } else { cout 无法连接。 endl; } return 0; }4. 关键细节与避坑指南实现算法只是第一步写出健壮、高效的代码才能在实际机试中拿满分。这里分享几个我踩过坑或者面试时常见的扣分点。4.1 坐标处理与边界检查这是最基础的也是最容易出错的。矩阵访问一定要先检查索引是否越界。在上面的代码中inBounds函数负责这个工作并且在checkLine等函数开头就调用。特别注意题目输入的坐标可能是以1为起始的例如第1行第1列而C中vector索引是从0开始的。务必在读取输入后将坐标转换为0-based索引或者在inBounds和访问时进行统一的转换。我建议在类内部统一使用0-based索引在接口处处理转换。4.2 “空白格”判断的逻辑一致性规则要求路径上的“中间点”必须是空白格值为0。但在不同情况下判断逻辑有细微差别在checkLine函数中我们检查的是起点和终点“之间”的格子不包括起点和终点本身。所以循环是for (int y startY 1; y endY; y)。这是正确的。在1个拐点情况下拐点C本身必须是空白格因为路径要经过它。我们在checkOneCorner中通过board[x1][y2] 0显式判断了。在2个拐点情况下扩展扫描法我们从起点/终点延伸时记录的就是沿途的空白格。所以reachableFromA和reachableFromB中的点天然就是空白格。在检查C1和C2连通时checkLine函数检查的是它们之间的线段同样不包含端点而端点C1和C2我们已经知道是空白所以逻辑一致。易错点在实现checkTwoCorners的“暴力遍历法”时即遍历所有格子作为C1和C2必须确保C1和C2是空白格并且要检查A-C1, C1-C2, C2-B这三段直线连通性。其中C1-C2的检查checkLine函数会检查C1和C2之间的格子但C1和C2本身在checkLine中不判断是否为空。因此如果C1或C2不是空白checkLine(c1, c2)可能错误地返回true如果它们值相等且中间为空。所以必须在调用checkLine前额外判断board[c1] 0 board[c2] 0。这也是为什么我推荐“扩展扫描法”它天然规避了这个陷阱。4.3 性能优化与小技巧虽然分类讨论法已经是O(N*M)的复杂度但仍有优化空间尤其是在checkTwoCorners函数中提前剪枝在checkTwoCorners中如果reachableFromA或reachableFromB为空可以直接返回false。使用集合或哈希优化查找上述代码中我们用了两层循环遍历reachableFromA和reachableFromB。如果这两个集合很大效率是O(L1*L2)。一个优化思路是对于reachableFromA中的每个点C1我们可以快速判断是否存在一个点C2在reachableFromB中且与C1同行或同列。这可以通过将reachableFromB按行和按列分别组织到unordered_mapint, vectorint中来实现将查找复杂度降至接近O(L1)。但在机试的棋盘规模下简单的双层循环通常已足够快代码可读性更重要。方向数组在BFS解法中使用dx[4] {-1, 1, 0, 0}和dy[4] {0, 0, -1, 1}来表示上下左右四个方向是标准且简洁的做法。4.4 测试用例设计自己编写代码时一定要设计全面的测试用例。针对这道题至少应包括基础功能直接相邻可连、同行隔空可连、同列隔空可连。一个拐点标准的L形连接两种可能的拐点情况。两个拐点Z形连接、U形连接需要绕一个弯。不可连情况图案不同、图案为空、路径被阻挡、拐点超过两个、起点终点相同。边界情况点在棋盘边缘、拐点正好在边界上、大棋盘压力测试。特殊棋盘全空棋盘、无空位棋盘。例如void test() { vectorvectorint board { {1, 0, 2, 0, 3}, {0, 0, 0, 0, 0}, {4, 0, 5, 0, 6}, {0, 0, 0, 0, 0}, {7, 0, 1, 0, 8} }; LinkGameSolver solver(board); assert(solver.canLink(0,0,4,2) true); // 两个1两个拐点相连 assert(solver.canLink(0,2,4,2) false); // 2和1图案不同 assert(solver.canLink(0,0,0,0) false); // 同一点 assert(solver.canLink(0,4,4,4) true); // 3和8直线被阻挡实际中间有空白应可连需具体看棋盘 cout All basic tests passed! endl; }5. 从解题到拿高分机试实战策略在华为OD机试的特定环境下解题正确只是第一步如何高效、稳定地拿到高分还需要一些实战策略。5.1 时间分配与编码顺序机试通常时长2-3小时2-3道题。连连看这类题属于中等难度建议分配时间在40-60分钟内完成。前5-10分钟仔细阅读题目用注释在代码开头明确写出输入输出格式、规则约束。绝对不要忽略任何细节比如坐标起始索引、拐点定义、空白表示等。10-20分钟在草稿纸上画图分析规则设计算法思路。优先选择实现简单、思路清晰的分类讨论法。画出流程图或伪代码。20-30分钟动手编码。按照模块化原则先实现checkLine这个基础函数并立刻用简单用例测试。然后依次实现checkOneCorner和checkTwoCorners每实现一个部分都进行测试。最后5-10分钟设计并运行多个测试用例包括边界情况。检查内存访问、边界条件。优化代码格式确保变量命名清晰。5.2 代码风格与可读性阅卷或自动评分系统也会关注代码质量。良好的风格能避免不必要的扣分甚至在人工复核时留下好印象。命名规范使用有意义的变量名如board,rows,cols而不是a,n,m。函数名用动词短语如canLink,checkLine。函数拆分就像上面的示例将不同功能拆分成小函数。这使逻辑清晰易于调试和阅读。一个巨大的main函数是扣分项。添加注释在关键算法步骤、复杂逻辑判断处添加简短注释解释“为什么这么做”。例如在checkOneCorner中注释为什么只检查两个特定拐点。错误处理对输入参数进行合法性检查如坐标越界并返回合理的值false。5.3 常见错误排查清单如果在自测时发现错误可以按以下清单快速排查坐标转换错误是否混淆了0-based和1-based索引所有输入坐标是否已统一转换边界条件遗漏checkLine中循环的起止条件是否正确是否正确处理了起点终点相邻的情况此时循环不会执行应返回true空白判断错误是否在应该检查拐点是否为空白的地方漏掉了检查尤其是在自己实现的暴力遍历法中。方向判断逻辑错误在1个拐点情况下检查(x1, y2)时是否正确地检查了A-(x1,y2)和(x1,y2)-B两条线注意这两条线一定是互相垂直的。重复计算与低效在checkTwoCorners的扩展扫描中是否将起点/终点本身也加入了可达集合这不会导致错误但会产生不必要的计算。内存与性能如果使用BFS是否使用了visited状态数组来避免重复访问同一状态状态是否包含(x, y, dir, corners)四要素5.4 如果时间允许BFS解法思路虽然分类讨论法更推荐但了解BFS解法能加深对问题的理解也是应对可能变体如“找最短拐点路径”的备选方案。BFS状态设计状态定义为(x, y, direction, cornerCount)。x, y: 当前所在格子坐标。direction: 当前前进方向0-上1-下2-左3-右-1表示起点无方向。cornerCount: 已经使用的拐点数量。BFS过程将起点状态(x1, y1, -1, 0)加入队列。当队列非空取出状态。如果当前位置是终点且board[x][y] board[x2][y2]则返回true。向四个方向探索下一个格子(nx, ny)。如果(nx, ny)不越界且是空白格或是终点。计算新的拐点数newCorner cornerCount (direction ! -1 dir ! currentDirection) ? 1 : 0。即如果当前不是起点且改变了方向拐点数1。如果newCorner 2且这个新状态(nx, ny, dir, newCorner)没有被访问过则加入队列和已访问集合。队列为空仍未找到终点返回false。BFS vs 分类讨论BFS更通用但需要维护状态和已访问集合代码量稍大在拐点限制很小≤2时分类讨论法通常更高效且易写。在机试中根据“哪条路让你更有信心在短时间内写对”来做选择。这道“连连看游戏”的机试题就像一场微型的软件设计演练。它考察的远不止是写出一个能跑的算法而是从问题抽象、方案抉择、细节实现到边界处理的全链条能力。我个人的体会是在平时练习时不要满足于通过样例要多问几个“为什么”为什么选这种算法这个边界条件怎么来的如果规则变了怎么办把这些想清楚再落到代码上你的代码才会更有韧性。最后一个小技巧在机试前可以专门找这种“网格搜索”、“路径判断”类题目集中练习形成自己的代码模板和条件反射上场时才能从容不迫。