1. 项目概述从“消消乐”游戏到华为OD机试最近在技术社区和求职论坛里华为ODOutsourcing Development的机试题目讨论热度一直很高。其中以经典游戏“消消乐”为背景的编程题因其趣味性和对算法、数据结构综合能力的考察成为了一个高频出现的考点。很多朋友无论是刚接触编程的新手还是准备面试的资深开发者都对这个题目既熟悉又头疼。熟悉是因为“消消乐”的规则直观易懂头疼则在于如何将游戏逻辑转化为清晰、高效、无bug的代码并能在华为OD机试的紧张环境下用C、Java、JavaScript或Python等不同语言优雅地实现。这个题目的核心远不止是“消除相同相邻元素”那么简单。它本质上是一个二维网格上的连通分量搜索与动态更新问题通常会结合重力下落和连锁消除的机制。在机试场景下它考察的不仅是你的编码能力更是你对问题建模、边界条件处理、算法选择如深度优先搜索DFS或广度优先搜索BFS以及代码健壮性的综合把控。网上能找到的很多代码示例要么过于简略只解决了“一次消除”要么逻辑复杂难以理解对于不同语言特性的利用也不够充分。因此我打算结合自己多次模拟和辅导的经验抛开那些华而不实的框架直接深入到代码骨髓里为你拆解这道题。我们将从最朴素的思路开始一步步迭代优化并给出在C、Java、JavaScript、Python四种主流语言下的实现要点与差异对比。目标很明确让你不仅“写得出来”更能“写得明白”、“写得高效”从容应对考场压力。2. 核心需求与游戏规则解析在动手写代码之前我们必须像产品经理一样把需求即游戏规则彻底吃透。华为OD的题目描述可能会有细微变化但万变不离其宗核心规则通常如下2.1 基础规则定义我们有一个M x N的二维网格每个格子内有一个字符或数字代表一种颜色的方块。例如A A B C A D B C A D B B消除条件当三个或三个以上同色方块在横向或纵向上紧密相邻即连通时这些方块会被消除。计分每次消除的方块数量即为本次得分或题目可能要求其他计分方式。重力下落消除后上方剩余的方块会因重力下落填补下方的空位。空位填充题目可能要求从网格顶部按某种规则生成新方块填补最上方的空位也可能简化处理将空位视为一种特殊符号如‘*’或‘0’。连锁反应一次消除导致下落填充后可能形成新的可消除组合游戏会持续进行直到没有可消除的方块为止。2.2 输入输出格式与边界条件机试题通常会严格定义输入输出这是拿分的基础必须一丝不苟。输入通常第一行是两个整数M和N代表网格的行数和列数。后续M行每行一个长度为N的字符串代表网格的初始状态。输出可能是最终消除后的网格状态也可能是消除的总次数或总得分。务必仔细阅读题目要求。边界条件网格可能为空M或N为0。方块种类字符集可能有限制。消除的阈值是3个还是其他数量需要确认。下落和填充的细节是从左到右、从右到左逐列下落还是整体处理。注意很多朋友栽在“看起来简单”的边界条件上。例如当一行同时存在多个可消除组时是分别消除还是合并消除下落时一列中可能有多个空位如何高效处理这些细节必须在设计算法前就想清楚。2.3 算法思路选型搜索与模拟面对这个二维网格我们的核心任务是如何高效地找出所有待消除的方块最直观的方法是遍历每个格子以其为起点向四个方向上、下、左、右进行搜索统计连通块大小。这里**深度优先搜索DFS和广度优先搜索BFS**都是可行的。DFS递归或栈思路简洁代码易于编写尤其适合描述“探索”过程。但对于极深的递归网格很大需要注意栈溢出风险在某些语言如Python中默认递归深度有限。BFS队列能避免递归过深的问题逻辑同样清晰。在搜索连通块时BFS和DFS的时间复杂度都是 O(M*N)因为每个格子最多被访问一次。我的建议是在机试的有限时间内选择你最熟悉、最能稳定发挥的方法。DFS递归写法通常更短小但要注意标记已访问节点防止重复计算和死循环。本文将主要以DFS递归为例进行讲解因为其逻辑更贴近人的直觉思考过程。3. 核心算法实现步骤拆解让我们把整个游戏过程分解成几个可复用的函数模块。这是写出清晰代码的关键。3.1 模块一查找所有可消除的方块组这是算法的核心。我们不能在遍历时直接修改原网格因为这会干扰后续的搜索判断。标准做法是先遍历一遍网格找出所有需要消除的方块位置记录到一个集合如Set或列表List中。步骤初始化一个空的集合to_remove用于存储待消除的坐标。遍历网格中的每一个格子(i, j)。如果该格子不是空位以其为起点进行DFS/BFS搜索寻找在水平或垂直方向上与其相连的、颜色相同的所有格子。如果找到的连通块大小 k(k为消除阈值通常是3)则将这个连通块中的所有坐标添加到to_remove集合中。注意在搜索过程中需要用一个额外的数据结构如visited集合或一个与网格同尺寸的布尔数组来标记本次搜索中已访问的格子防止重复访问。但注意这个visited是局部于一次连通块搜索的搜索完成后应清空或新建因为下一个格子的搜索需要重新开始。关键技巧搜索时我们只关心当前连通块。可以使用一个列表current_group在搜索过程中动态记录成员坐标。3.2 模块二执行消除与网格更新获得to_remove集合后执行消除就简单了。遍历to_remove中的每个坐标(i, j)将网格中对应位置设置为代表“空”的值如‘*‘,‘0‘, 或None。这里有一个易错点如果题目要求消除后立即下落那么消除和下落最好是分开的两步。先统一消除再统一处理下落逻辑更清晰。3.3 模块三模拟重力下落下落是另一个小难点。最朴素的方法是对于每一列从底部向上遍历遇到非空方块就将其向下“沉”直到遇到底部或其他方块。高效的做法对每一列j单独处理。使用一个指针write_row从该列的最后一行M-1开始向上移动这个指针指向下一个可以放置方块的位置。再用另一个指针read_row从最后一行开始向上遍历。当read_row遇到一个非空方块时将其复制到write_row的位置然后write_row上移一格。当read_row遍历完该列后write_row以上的所有位置都应该被设置为空位。这个过程类似于数组操作中的“移除特定元素并向一端靠拢”是线性时间复杂度 O(M) 每列。3.4 模块四驱动主循环将上述模块组合起来形成游戏主循环while True: to_remove find_all_matches(grid) if to_remove is empty: break # 没有可消除的游戏结束 remove_blocks(grid, to_remove) apply_gravity(grid) # 可选填充顶部空位 (fill_new_blocks(grid))循环的终止条件是在一轮完整的“查找-消除-下落”后没有找到任何新的可消除方块。4. 多语言代码实现与解析不同语言有其独特的语法特性和标准库实现同一算法时代码风格和性能考量点也不同。下面我们分别看看。4.1 C 实现要点C追求效率和精细的内存控制。#include iostream #include vector #include set using namespace std; class Solution { public: vectorvectorchar candyCrush(vectorvectorchar board) { if (board.empty()) return board; int m board.size(), n board[0].size(); bool found true; // 主循环 while (found) { found false; // 1. 标记待消除 vectorvectorbool toRemove(m, vectorbool(n, false)); for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] 0) continue; // 横向检查 (至少3个) if (j 2 n board[i][j] board[i][j1] board[i][j] board[i][j2]) { int k j; while (k n board[i][j] board[i][k]) { toRemove[i][k] true; found true; k; } } // 纵向检查 (至少3个) if (i 2 m board[i][j] board[i1][j] board[i][j] board[i2][j]) { int k i; while (k m board[i][j] board[k][j]) { toRemove[k][j] true; found true; k; } } } } if (!found) break; // 2. 执行消除置为‘0’ for (int i 0; i m; i) { for (int j 0; j n; j) { if (toRemove[i][j]) board[i][j] 0; } } // 3. 重力下落 for (int j 0; j n; j) { int writeRow m - 1; // 从下往上将非‘0’元素下沉 for (int i m - 1; i 0; --i) { if (board[i][j] ! 0) { board[writeRow--][j] board[i][j]; } } // 将剩余顶部位置置为‘0’ while (writeRow 0) { board[writeRow--][j] 0; } } } return board; } };C注意事项容器选择使用vectorvectorchar表示网格vectorvectorbool标记待消除位置。避免使用setpairint,int来标记因为二维bool向量访问效率更高。搜索优化上述代码采用了直接遍历标记而非DFS因为在已知消除规则是“三连”时直接检查连续三个相同元素更简单高效。这是一种针对特定规则的优化。内存与引用函数参数使用vectorvectorchar board通过引用修改原数组避免拷贝开销。下落操作内层下落循环是O(M)的且是原地操作没有额外内存分配。4.2 Java 实现要点Java代码结构清晰注重面向对象和异常安全。public class CandyCrush { public int[][] candyCrush(int[][] board) { int m board.length, n board[0].length; boolean found true; while (found) { found false; boolean[][] toRemove new boolean[m][n]; // 标记待消除 for (int i 0; i m; i) { for (int j 0; j n; j) { int val Math.abs(board[i][j]); // 使用绝对值方便后续处理 if (val 0) continue; // 横向检查 if (j 2 n val Math.abs(board[i][j1]) val Math.abs(board[i][j2])) { for (int k j; k n Math.abs(board[i][k]) val; k) { toRemove[i][k] true; found true; } } // 纵向检查 if (i 2 m val Math.abs(board[i1][j]) val Math.abs(board[i2][j])) { for (int k i; k m Math.abs(board[k][j]) val; k) { toRemove[k][j] true; found true; } } } } if (!found) break; // 消除将标记位置的值取反或置0 for (int i 0; i m; i) { for (int j 0; j n; j) { if (toRemove[i][j]) { board[i][j] -Math.abs(board[i][j]); // 标记为负数便于区分 } } } // 重力下落 for (int j 0; j n; j) { int writeRow m - 1; for (int i m - 1; i 0; i--) { if (board[i][j] 0) { // 只处理未消除的正数方块 board[writeRow--][j] board[i][j]; } } while (writeRow 0) { board[writeRow--][j] 0; } } } return board; } }Java注意事项数组与集合使用基本类型二维数组int[][]和boolean[][]性能最好。ArrayList等集合类在这里可能带来不必要的开销。消除标记技巧一个常见的技巧是将待消除的值置为它的负数。这样在下落阶段可以通过判断值的正负来区分是否需要保留无需额外的toRemove数组。但上述代码保留了toRemove数组以求逻辑清晰。绝对值比较在比较时使用Math.abs()是为了处理可能已经被标记为负数的值确保比较的正确性。代码风格Java代码通常更冗长但结构非常规整利于阅读和调试。4.3 JavaScript 实现要点JavaScript在浏览器或Node.js环境中运行代码灵活但要注意数组和循环的性能。function candyCrush(board) { if (!board || board.length 0) return board; const m board.length, n board[0].length; let found true; while (found) { found false; const toRemove Array.from({length: m}, () new Array(n).fill(false)); // 1. 查找可消除项 for (let i 0; i m; i) { for (let j 0; j n; j) { if (board[i][j] 0) continue; // 横向检查 if (j 2 n Math.abs(board[i][j]) Math.abs(board[i][j1]) Math.abs(board[i][j]) Math.abs(board[i][j2])) { for (let k j; k n Math.abs(board[i][k]) Math.abs(board[i][j]); k) { toRemove[i][k] true; found true; } } // 纵向检查 if (i 2 m Math.abs(board[i][j]) Math.abs(board[i1][j]) Math.abs(board[i][j]) Math.abs(board[i2][j])) { for (let k i; k m Math.abs(board[k][j]) Math.abs(board[i][j]); k) { toRemove[k][j] true; found true; } } } } if (!found) break; // 2. 执行消除 for (let i 0; i m; i) { for (let j 0; j n; j) { if (toRemove[i][j]) { board[i][j] -Math.abs(board[i][j]); } } } // 3. 重力下落 for (let j 0; j n; j) { let writeRow m - 1; // 从下往上移动非负值 for (let i m - 1; i 0; i--) { if (board[i][j] 0) { board[writeRow--][j] board[i][j]; } } // 顶部填充0 while (writeRow 0) { board[writeRow--][j] 0; } } } return board; }JavaScript注意事项数组初始化Array.from({length: m}, () new Array(n).fill(false))是创建二维布尔数组的简洁方法。避免使用new Array(m).fill(new Array(n).fill(false))这会导致所有行引用同一个子数组。严格相等比较时使用。注意0和空值null/undefined的区别。性能在JavaScript中嵌套循环访问二维数组是性能敏感操作。保持算法逻辑简洁高效至关重要。Math.abs的使用借鉴了Java版本的技巧。输出机试环境可能要求将结果打印到控制台或返回注意题目具体要求。4.4 Python 实现要点Python代码以简洁著称利用列表推导式和切片操作可以写出非常优雅的代码但要注意其浅拷贝/深拷贝问题。from typing import List def candyCrush(board: List[List[int]]) - List[List[int]]: if not board: return board m, n len(board), len(board[0]) found True while found: found False # 使用集合记录待消除坐标避免重复 to_remove set() # 1. 查找所有可消除的连续块 (3) for i in range(m): for j in range(n): if board[i][j] 0: continue # 横向检查 if j 2 n and abs(board[i][j]) abs(board[i][j1]) abs(board[i][j2]): k j while k n and abs(board[i][k]) abs(board[i][j]): to_remove.add((i, k)) found True k 1 # 纵向检查 if i 2 m and abs(board[i][j]) abs(board[i1][j]) abs(board[i2][j]): k i while k m and abs(board[k][j]) abs(board[i][j]): to_remove.add((k, j)) found True k 1 if not found: break # 2. 执行消除 for i, j in to_remove: board[i][j] -abs(board[i][j]) # 标记为负 # 3. 重力下落 for j in range(n): # 收集该列所有未消除的方块正数 column_vals [board[i][j] for i in range(m) if board[i][j] 0] # 从底部开始填充 for i in range(m-1, -1, -1): if column_vals: board[i][j] column_vals.pop() else: board[i][j] 0 return boardPython注意事项类型提示使用typing.List增加代码可读性对IDE友好。集合的使用使用set()存储待消除坐标(i, j)可以自动去重特别适合处理交叉位置的方块既满足横向消除又满足纵向消除。链式比较a b c是Python的语法糖非常简洁。下落操作的Pythonic写法通过列表推导式[board[i][j] for i in range(m) if board[i][j] 0]快速过滤出该列需要保留的方块然后从底部填充。这种方法逻辑清晰但会创建额外的列表。对于追求极致性能的场景也可以使用类似C/Java的双指针原地操作。列表的可变性Python中列表是可变对象函数内修改会直接影响传入的实参。这符合题目要求。5. 常见陷阱、调试技巧与性能优化即使算法思路正确实现时也容易掉进一些坑里。下面是一些实战中总结的经验。5.1 典型错误与边界情况原地修改与搜索干扰最经典的错误是在第一遍遍历查找待消除方块时找到一组就立刻将其消除置空。这会导致后续遍历时基于新的网格状态进行判断可能漏掉一些因为本次消除才露出来的可消除组合或者错误地将新落下来的方块纳入当前轮的判断。务必坚持“先标记后消除”的两步走策略。连通块搜索的重复计数使用DFS/BFS时如果没有正确标记“已访问”可能会对同一个连通块重复搜索多次导致超时或逻辑错误。确保每个格子在一次主循环的“查找”阶段只被一个连通块搜索访问一次。下落逻辑错误下落时必须按列独立处理并且从下往上遍历。如果从上往下遍历会导致上方方块下落覆盖下方还未检查的方块造成数据丢失。双指针读指针和写指针是清晰且高效的方法。空值处理对于代表空位的值如0,‘*‘,None在查找连通块时要首先跳过避免将它们也纳入比较。网格为空或单行/单列在代码开头检查M和N如果任一为0应直接返回原网格或空结果。5.2 调试与测试用例设计在机试或自己练习时设计好的测试用例能帮你快速定位问题。最小用例1x1网格2x2网格无法消除。单次消除构造一个明确的3连或4连检查是否能正确消除并下落。连锁消除构造一个消除后上方方块下落能形成新的可消除组合的情况检查主循环是否能正确进行第二轮。交叉消除构造一个“T”型或“L”型的连通块检查集合或标记数组是否能正确包含所有方块且不会重复。满消除所有方块都可消除检查程序是否能正确清空网格并结束。列下落复杂情况一列中有多个空位间隔分布检查下落算法是否能正确整理。调试技巧在关键步骤后如标记完to_remove执行完下落打印出当前的网格状态。可视化是调试网格类问题最有效的手段。5.3 高级优化思路对于追求极致性能或者应对非常大网格的变种题可以考虑以下优化增量更新在一次消除下落完成后并非所有区域都需要重新全盘扫描。只有那些发生变化区域及其周边可能产生新的可消除组合。可以记录发生变化的行/列范围下一轮只在这些区域内进行查找。但这会大大增加代码复杂度在普通机试题中通常不需要。并查集Union-Find对于查找连通块并查集是另一种数据结构选择。它可以近乎O(1)的时间合并相邻相同方块最后统计每个集合的大小。但实现起来比DFS/BFS稍复杂且同样需要处理“先合并再判断”的流程。位运算标记如果方块种类有限比如少于32种可以考虑用整数的位来标记待消除状态可以节省空间和提高某些操作速度。但这属于非常极致的优化可读性会下降。我的建议在华为OD机试这种时间有限的环境下优先保证代码的正确性和清晰度。使用最直接的“标记-消除-下落”循环配合DFS/BFS或直接遍历检查完全足够应对题目要求。在代码都写对的基础上再去考虑那些花哨的优化。6. 从解题到拿高分机试实战策略理解了算法和代码如何在考场上稳定发挥拿到高分审题审题审题花5分钟仔细读题用笔圈出输入格式、输出格式、消除规则几个相连是否包含斜向、计分方式。误解题意是导致提交失败的最主要原因。先画图再编码。在草稿纸上画一个小网格模拟一下题目给的例子理清“查找”、“标记”、“消除”、“下落”的数据流。这个过程能帮你发现逻辑漏洞。模块化编程。就像本文分解的那样把findMatches,crush,drop写成独立的函数。即使时间再紧也要先写出函数框架和注释。这有利于调试也方便你万一时间不够可以向考官展示清晰的思路。先实现后优化。第一目标是写出一个能通过基本用例的、逻辑正确的版本。哪怕用了最笨的双重循环全盘扫描。确保正确后如果时间允许再思考是否有更优雅的写法。充分测试。利用IDE或在线编程环境提供的自定义测试功能跑一遍你自己设计的小用例。特别是边界情况。华为OD的机试平台通常允许自测。代码风格。虽然不占主要分数但整洁的代码、清晰的变量名、必要的注释能体现你的专业素养。避免使用a,b,c这种魔法变量。时间管理。如果一道题卡住超过20分钟果断检查核心逻辑或者先跳过做其他题如果有多题。有时候回头再看可能瞬间发现错误。这道“消消乐”题目就像一面镜子能照出程序员的基础功底和思维习惯。它不要求你知道多么高深的数据结构但要求你对基础算法搜索、模拟有扎实的掌握对代码细节有严谨的把控。希望这篇超详细的解析能帮你剥开它趣味性的外壳看到其中严谨的算法内核并在下一次机试中自信地敲出完美的代码。