1. 项目概述与核心思路拆解最近在准备华为OD机试的朋友应该对“数值同化”或者“矩阵中非1的元素个数”这类题目不陌生。这题本质上是一个经典的多源广度优先搜索BFS模拟问题它考察的是对图遍历、状态模拟和时间维度处理的理解。题目描述了一个m*n的矩阵里面有0、1、2三种值。其中1是“感染源”每过1秒它就会向上下左右四个方向“同化”感染值为0的格子把它们变成1。而值为2的格子是“免疫体”永远不会被同化。题目会给你一个初始矩阵并把左上角(0,0)强制设为1问你“经过足够长时间后”矩阵中不是1的元素也就是剩下的0和2还有多少个。这题为什么值得拿出来单独讲因为它完美地融合了几个机试高频考点二维矩阵的遍历、BFS的层序遍历思想、以及模拟过程中的状态管理。很多同学一看到“每经过1S”就想着用循环去模拟每一秒结果要么超时要么逻辑写成一团乱麻。其实只要你理解BFS的“层”就天然对应着“秒”这道题的复杂度就能从O(kmn)降到O(m*n)其中k是模拟的秒数。接下来我会用C带你从零开始一步步拆解这道题不仅给出能AC的代码更会讲清楚每一步背后的“为什么”以及我在刷题和面试中总结出来的避坑技巧。2. 问题深度解析与算法选型2.1 为什么是BFS而不是DFS或直接模拟这是理解本题的第一个关键。题目中“每经过1S将上下左右值为0的元素同化为1”这句话描述的是一个波面扩散的过程。新的1产生后在下一秒又成为新的扩散源。这个过程有两个重要特征等距扩散从某个1出发它到被它同化的0格子的“感染”步数即时间是最短路径。层序性所有在第t秒被同化的格子一定是在第t-1秒时某个1的邻居。这两个特征正是广度优先搜索BFS的核心。BFS保证我们总是先处理距离源点更近的节点每一轮遍历就对应着“一秒”的扩散。如果我们用深度优先搜索DFS它会一条路走到黑无法保证“同时”扩散的效果模拟出的时间顺序是错的。而如果用最简单的双层循环每秒去扫描整个矩阵即直接模拟假设矩阵很大且需要很多秒才能完全扩散时间复杂度会非常高可能达到O(Tmn)其中T是扩散总秒数在极端情况下如一个狭长的通道T可能接近mn导致效率低下。BFS方案则巧妙地将“时间”维度转化为“队列的层”。我们初始化队列时把所有初始就是1的格子本题是(0,0)加入队列。然后每次处理一“层”记下当前队列的长度size然后进行size次出队操作。对于每个出队的节点检查其四个邻居如果邻居是0就将其同化为1并加入队列。这size次操作就模拟了“一秒”内所有当前感染源同时发起的扩散。处理完这一层再处理下一层直到队列为空。此时所有能被同化的0都已被同化剩下的0和2就是我们的答案。2.2 输入处理与数据结构设计华为OD的机试题输入通常是标准输入格式比较固定。对于本题输入分两部分第一行两个整数m和n代表矩阵的行数和列数。后续m行每行n个整数代表矩阵的初始值。我们需要将其读入并存储。一个易错点是题目说“将矩阵的[0,0]元素修改成1”。这意味着无论输入的第一个数是什么我们都需要在初始化后将matrix[0][0]的值强制设置为1。这是一个关键细节如果漏了遇到输入中(0,0)位置初始是2的用例就会出错。数据结构方面矩阵存储使用vectorvectorint这是C中最直观的二维数组表示。队列使用queuepairint, int存储待处理的感染源坐标。方向数组用一个vectorpairint, int dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}来表示上下左右四个方向这样在遍历邻居时代码更清晰避免写四个重复的if判断。注意有些同学喜欢用两个队列或者一个队列配合nullptr来区分层但在这种二维坐标BFS中最清晰且不易出错的方法就是我在上面提到的“记录当前层大小”的方法。即在每一轮扩散开始前int currentLevelSize q.size();然后用一个for循环处理这么多个节点。2.3 算法流程与边界条件理清思路后完整的算法流程如下初始化读取m,n和矩阵数据。创建队列q。设置初始感染源将matrix[0][0]设为1并将坐标(0,0)加入队列q。这里要注意如果初始matrix[0][0]就是2免疫体根据题意我们依然要把它改成1但它作为1无法扩散因为它的邻居如果是0才能被同化所以队列初始可能只有一个无法行动的点最终结果就是矩阵中所有的0和2包括这个被强行变成1的“假1”位置实际上它应该被算作非1这里是个大坑。实操心得这是本题最大的一个陷阱仔细读题“将矩阵的[0,0]元素修改成1”。这意味着(0,0)位置最终必须是1。但如果它输入时是2你把它改成1它这个“1”具备同化能力吗题目描述“值为1的元素具备同化特性”并没有说“被修改成1的元素”不具备。所以从逻辑上这个新1应该具备同化能力。但是在计算最终“非1元素个数”时这个位置已经被算作1了。所以我们的算法逻辑必须包含这一步。BFS扩散 a. 当队列不为空时获取当前层节点数sz q.size()。 b. 循环sz次每次从队列取出一个坐标(x, y)。 c. 遍历该坐标的四个邻居(nx, ny)。 d. 如果(nx, ny)在矩阵范围内且matrix[nx][ny] 0则将其值改为1并将其坐标加入队列。统计结果BFS结束后遍历整个矩阵统计值不为1的格子数量即值等于0或2的格子。输出将统计结果输出。边界条件与特殊情况处理矩阵大小为0虽然题目可能不会给但稳健的代码应该检查if (m 0 || n 0) return 0;。初始点就是2如上所述按题目要求修改为1并加入队列。但它的邻居是0才会被感染所以不影响算法正确性。没有0可同化如果矩阵里全是2和1除了(0,0)那么队列初始只有(0,0)它没有值为0的邻居BFS会立刻结束。统计时所有2都被算入结果正确。多个初始感染源本题明确只有一个初始感染源(0,0)。但BFS框架天然支持多源起点只需在初始化时将多个源点都入队即可。这是一个很好的扩展点。3. C代码实现与逐行解读理解了算法我们来看C实现。我会提供一份注释详尽的代码并解释关键行背后的考量。#include iostream #include vector #include queue using namespace std; int main() { int m, n; cin m n; // 边界检查 if (m 0 || n 0) { cout 0 endl; return 0; } // 1. 读取矩阵并初始化 vectorvectorint matrix(m, vectorint(n)); for (int i 0; i m; i) { for (int j 0; j n; j) { cin matrix[i][j]; } } // 2. 根据题意强制将(0,0)位置设为1 // 注意无论它原来是0还是2现在它都是具有扩散能力的1。 matrix[0][0] 1; // 3. 初始化BFS队列并将初始感染源入队 queuepairint, int q; q.push({0, 0}); // 4. 方向数组表示上下左右四个邻居的坐标偏移量 vectorpairint, int directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 5. BFS模拟扩散过程 while (!q.empty()) { int levelSize q.size(); // 当前“秒”需要处理的感染源数量 for (int i 0; i levelSize; i) { auto [x, y] q.front(); q.pop(); // 遍历当前感染源的四个邻居 for (auto dir : directions) { int nx x dir.first; int ny y dir.second; // 检查邻居坐标是否合法并且是否为可被同化的0 if (nx 0 nx m ny 0 ny n matrix[nx][ny] 0) { matrix[nx][ny] 1; // 同化 q.push({nx, ny}); // 新的感染源入队 } } } // 当前层所有节点处理完毕代表过去了一秒循环继续处理下一层 } // 6. 统计非1元素即剩余的0和2的个数 int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] ! 1) { count; } } } // 7. 输出结果 cout count endl; return 0; }关键代码解读与技巧auto [x, y] q.front();(C17结构化绑定)这是C17的特性可以方便地将pair解包到两个变量中。如果你的编译环境不支持C17可以写成int x q.front().first; int y q.front().second;。在机试环境中通常支持C11/14为了最大兼容性使用传统写法更稳妥。levelSize的使用这是实现“层序”BFS的核心。在while循环开始时记录当前队列大小然后内层for循环只处理这么多节点。这保证了我们是在处理“同一秒”产生的所有新感染源。内层循环结束后队列里剩下的就是“下一秒”要处理的源了。方向数组directions将四个方向的偏移量存入数组用循环遍历比写四个if语句更简洁不易遗漏也便于修改如果题目变成八方向扩散只需修改这个数组。条件判断顺序在检查邻居时if (nx 0 nx m ny 0 ny n matrix[nx][ny] 0)一定要先判断坐标合法性再访问数组否则可能发生数组越界导致运行时错误。空间复杂度我们使用了一个队列最坏情况下所有格子都入队一次所以额外空间复杂度是O(m*n)。矩阵本身是输入数据不计入额外空间。这个复杂度是可以接受的。4. 测试用例分析与调试技巧写完代码不代表万事大吉用各种边界和特殊的测试用例去验证才是保证AC率的王道。我建议大家准备机试时养成自己设计测试用例的习惯。测试用例设计基础用例题目示例输入 4 4 0 0 0 0 0 2 2 2 0 2 0 0 0 2 0 0 输出9用于验证基本逻辑是否正确。最小矩阵输入 1 1 0 输出0解释只有(0,0)被设为1后没有非1元素。初始点即为2输入 3 3 2 0 0 0 2 0 0 0 0 输出?手动推导将(0,0)从2改为1。这个1可以感染右边的(0,1)0-1。新感染的(0,1)是1但它上下左右邻居是(0,0)1(0,2)0(1,1)2。所以它能感染(0,2)。(0,2)变成1后它的邻居(1,2)是0可以感染...最终所有0都会被感染。剩下的非1元素就是初始的2(1,1)和(2,0)?等等(2,0)初始是0会被感染吗(1,0)是0会被(0,0)或(1,1)感染吗(1,1)是2免疫。所以(1,0)可以被(0,0)感染(2,0)可以被(1,0)感染。最终矩阵为 1 1 1 1 2 1 1 1 1 非1元素只有中间的2所以输出应为1。用程序跑一下验证。全2矩阵输入 2 2 2 2 2 2 输出4解释将(0,0)改为1但它周围全是2无法扩散。最终矩阵为 1 2 2 2 非1元素有3个2加上(0,0)这个1不对(0,0)现在是1所以非1元素是3个。等等题目问的是“矩阵中有多少个元素是0或2”。(0,0)现在是1所以不算。答案是3。这里再次提醒统计的是最终状态。全0矩阵输入 3 3 0 0 0 0 0 0 0 0 0 输出0解释所有0都会被同化成1。长条形通道考验BFS是否超时输入 1 1000 0 0 0 ... (1000个0)输出应为0。这个用例可以测试你的算法是否是O(m*n)的。如果是每秒扫描全矩阵的模拟法会非常慢。调试技巧与常见错误忘记重置(0,0)为1这是最致命的错误会导致第一个样例就过不了。务必在读入数据后立刻执行matrix[0][0] 1;。BFS层控制错误错误写法是在while循环里不记录levelSize直接while(!q.empty()) { auto [x,y]q.front(); q.pop(); ... }。这样会把所有新加入的节点在同一层处理完无法区分“秒”但有趣的是对于这道题最终结果是一样的因为无论是否分层最终所有0都会被感染。但分层是更规范、更符合题意且易于扩展到“求完全同化所需时间”等变体题目的写法。数组越界在访问matrix[nx][ny]前务必检查nx和ny的合法性。使用int还是bool标记已访问本题中我们将被同化的0直接修改为1这本身就起到了“已访问”标记的作用。所以不需要额外的visited数组。这是一种原地修改的技巧节省空间。输出格式务必只输出一个整数不要添加任何多余的空格或换行除非题目要求。cout count endl;是标准做法。5. 性能优化与扩展思考虽然上述解法已经足够通过机试但我们还可以从工程和扩展角度思考更多。性能优化点输入输出加速对于C在涉及大量数据读入时比如矩阵很大可以关闭C标准流与C标准流的同步以提升速度。在main函数开头加入ios::sync_with_stdio(false); cin.tie(nullptr);注意使用了这个之后就不要混用printf/scanf和cout/cin了。队列存储优化对于坐标我们用了pairint,int。也可以使用两个整数队列queueint qx, qy或者将坐标编码成一个整数int pos x * n y来存储解码时x pos / n, y pos % n。这在某些对内存极其敏感的场景下可能有用但本题中必要性不大。扩展思考如果要求输出完全同化所需的时间秒数很简单在BFS的while循环中增加一个int time 0;变量。在每一层每秒开始处理前如果队列不为空且当前层有节点能感染新节点即发生了扩散则time。或者更简单time初始为-1每处理完一层time最后time就是所需时间。注意处理初始状态。如果初始感染源有多个且位置由输入给出初始化队列时将所有给定的感染源坐标入队即可。其他逻辑不变。如果2不是永久免疫而是只能抵抗一定时间比如3秒这就需要为每个格子增加一个状态或计时器。我们可以用matrix存储当前值1或2再用一个额外的vectorvectorint resistTime记录每个2还能抵抗的秒数。BFS过程中当遇到值为2的邻居时不立即同化而是将其抵抗时间减1。当抵抗时间减到0时将其值改为1并加入队列。这时的BFS层循环需要携带“当前时间”信息。如果同化速度不同比如有的1每秒感染一格有的每秒感染两格这就变成了多速度BFS或者Dijkstra算法求最短时间的模型。需要使用优先队列最小堆队列元素存储坐标和该感染源“生效”的时间点每次取出时间最小的节点进行处理。把这些扩展想清楚你对BFS和图遍历的理解会上一个大台阶。机试的题目往往就是这些基础算法的变体和组合。6. 华为OD机试实战注意事项结合我个人的经验和网上众多网友的分享在华为OD机试中遇到此类题目还有一些考场上的实用建议环境熟悉华为OD机试通常是在牛客网之类的平台进行使用在线IDE。提前熟悉环境知道怎么输入测试用例怎么运行怎么调试。有些平台不支持C17所以代码尽量用C11/14的通用写法。时间分配一道题通常有30-50分钟。花5-10分钟彻底理解题意设计算法和数据结构画出示意图。然后20-25分钟编码。最后留出5-10分钟进行测试和调试。不要一开始就想一个完美方案先写出一个能工作的版本比如朴素的逐秒模拟确保逻辑正确再考虑优化比如改成BFS。注释与命名写清晰的变量名和必要的注释。虽然不占分但在你回头检查或面试官看你代码时能极大提升可读性。比如q可以命名为infectionQueuedirs命名为directions。自测一定要用题目给的样例和上面提到的边界用例自己测一遍。在线平台通常有“自测”功能输入样例看输出是否一致。心态调整如果第一次没AC不要慌。看错误信息是编译错误、运行错误段错误、数组越界、还是答案错误编译错误检查语法运行错误重点检查数组访问和递归/队列的边界条件答案错误则用更多的小数据量用例进行逻辑排查。关于本题的变体我搜索到的历史真题叫“矩阵中非1的元素个数”和“数值同化”是同一道题。华为OD的题目库会有更新和重组但核心考点万变不离其宗。掌握BFS这道题就是送分题。最后代码的鲁棒性很重要。即使题目保证输入有效加上基本的边界判断如m,n是否为正数也是一个好习惯。写完代码后在脑海中或者纸上模拟一下整个BFS过程尤其是队列的变化这能帮你发现很多潜在的逻辑漏洞。这道“数值同化”题就像一把钥匙帮你打开了利用BFS解决模拟类问题的大门。在类似的“腐烂的橘子”、“岛屿数量”、“墙与门”等LeetCode题目中你都能看到它的影子。把这里的层序遍历、方向数组、原地修改标记等技巧掌握熟练再遇到这类题目时你就能快速识别并套用模型从而在紧张的机试中节省宝贵的时间。