拓冰网站定制 
准备华为OD机考的朋友或者正在刷C卷题库的同学应该对这道“返回矩阵中非1的元素个数”不陌生。它经常以“数值同化”的名字出现在题库里一个二维矩阵有些位置是1有些位置是01会像水波一样向上下左右扩散把碰到的0同化成1最后问整个矩阵中还剩下多少个元素不是1。这道题难度不大套路却非常典型属于“会者不难难者不会”的代表。本文就把它彻底拆开用Java、Python、JS、C、C五种语言各写一版完整题解并且把我自己在刷题和实际机考准备过程中踩过的坑一起列出来。1. 题面还原与样例推演先锁定“同化”的传播规则1.1 题面到底长什么样先说题面。这不是一道需要读半天的题但“数值同化”这四个字确实容易让人想偏。常见描述是这样的给定一个 m 行 n 列的矩阵矩阵中的每个格子取值为0、1、2。其中1表示“同化源”每一轮同化源会将它上下左右四个方向相邻的0变成12表示障碍物1不能同化2。经过足够多轮直到整个矩阵不再发生变化请返回矩阵中非1元素的个数也就是最终值为0或2的格子数量。请注意返回的是“最终矩阵里不等于1的元素个数”不是问“一共同化了多少个格子”也不是问“需要几轮同化完成”。有些同学一上来就开始数初始矩阵里有多少个0那就是把“同化前”和“同化后”搞混了。“数值同化”这个叫法在华为OD机考C卷的题库里经常和“返回矩阵中非1的元素个数”并列出现。我个人理解“同化”两个字强调的就是传播过程1是源头0是被传染目标2是围墙。理解了这一点后面所有代码都是围绕“从所有1出发沿四方向感染相邻0”来写。1.2 手推样例为什么不是一次性扩散用一个3行3列的矩阵来推一遍。输入3 3 1 0 0 0 0 0 0 0 1这一步很多第一次做这道题的同学会算错。有人觉得上下左右四个方向“一步到位”直接把两个1周围的所有0全部变成1然后数一数还有没有0。按照这个错误思路第一轮后矩阵会变成1 1 0 1 0 1 0 1 1看起来剩一个0。但这不是真正的同化过程因为同化是每轮只向相邻格子走一格。真正的过程是这样的第1轮左上角的1感染0,1和1,0右下角的1感染1,2和2,1。第2轮中心1,1被0,1、1,0、1,2、2,1任意一个感染同时0,2被0,1感染2,0被1,0感染。第3轮以后不再变化矩阵全部变成1。最终矩阵里没有非1元素答案是0。能看到同化是按层扩散的“数值”一层一层往外“同化”这就是标准的BFS层级传播。如果直接用“一步到位”的思维去写代码要么多算要么少算。1.3 最容易忽略的两个边界场景边界场景一整个矩阵没有1。这时没有同化源矩阵会发生任何变化吗不会。所以所有格子都是非1元素答案就是 m 乘以 n。边界场景二矩阵中有1同时有2。比如3 3 1 1 0 2 0 0 0 0 0左上角的两个1会把0,2、1,1、2,0都感染成1然后继续往下扩散。但1,0位置的2是墙它挡住了左侧这一列仔细看其实2下面还有2,02,0会被1,1或2,1感染不一定非要穿过2。所以只有被2完全隔开、四周又没有任何1能间接到达的0区域才会永远保持为0。这种情况在真题里出现过读题时别默认矩阵里只有0和1。2. 为什么首选多源BFS从“感染扩散”看算法选型2.1 模拟逐轮扩散的问题看到“每一轮向上下左右扩散”这个描述第一反应是写一个while循环每轮扫描全矩阵把0变成1直到某一轮没有发生任何变化。这个思路本身没错但有个致命问题效率低。假设矩阵是1000乘1000同化传播要1000轮才能结束每一轮都扫描全部100万个格子总共就是10亿次操作。在机考环境下这个复杂度很可能超时。更关键的是逐轮模拟还必须小心处理“同一轮内已经被改成1的格子是否参与本轮扩散”这种边界问题很容易写错。所以这道题的标准解法不是逐轮模拟而是把初始所有1一次性入队做多源BFS。BFS天然自带“层级”属性队列弹出的顺序就是感染顺序不需要额外记录轮次。2.2 多源BFS的两阶段初始化队列 逐层扩展多源BFS和普通BFS的唯一区别就是起始时队列里不是只有一个点而是所有满足条件的点一起进去。这道题里所有初始值为1的格子都是起点。第一阶段读入矩阵的同时把值为1的坐标全部加入队列。第二阶段从队列中逐个取出坐标检查上下左右四个邻居如果邻居是0就把它改成1并加入队列如果邻居是2或者已经变成1就跳过。为什么改成1之后要立刻入队因为BFS的核心是“每个节点只入队一次”。把0改成1相当于给这个格子打上了“已访问”标记既防止它被其他源重复处理又保证它作为新的传播源继续感染后面的格子。如果只标记不入队同化链条就会断掉。用一个生活化类比把多个水龙头放在一个满是干泥土的网格里水从每个水龙头同时向四周渗透遇到石头2就绕开已经湿掉的土地不会再次变干。多源BFS就是同时打开所有水龙头水位边界的扩张顺序就是BFS的队列顺序。2.3 DFS能不能做能用但有代价有同学会问这种连通区域题不是可以用DFS吗确实可以。对于没有障碍的版本DFS递归遍历所有0也能统计出结果。但DFS在矩阵题里有两个隐患第一递归深度风险。如果矩阵是1000乘1000一条路径可能递归几百上千层Java和Python默认栈深度很可能扛不住直接栈溢出。第二DFS的“深度优先”性质和“同化逐层扩散”的直觉不一致排查逻辑错误时更费劲。所以我的建议是矩阵连通类题目只要题目描述里出现“向四周扩散”“感染”“同化”“最短步数”这些字眼优先写BFS。这道题也不例外。3. 五种语言的完整实现与差异点3.1 Java队列用ArrayDeque比LinkedList更稳Java里最常见的队列写法是 LinkedList但在算法题里我更推荐 ArrayDeque。两者的区别在于ArrayDeque基于循环数组实现入队出队都是常数时间而且不会产生LinkedList那种大量小对象的分配开销。这道题的队列里存的是坐标用 int[] 数组存即可。完整实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); int[][] grid new int[m][n]; Queueint[] queue new ArrayDeque(); for (int i 0; i m; i) { for (int j 0; j n; j) { grid[i][j] sc.nextInt(); if (grid[i][j] 1) { queue.offer(new int[]{i, j}); } } } // 整个矩阵没有1不需要同化所有元素都是非1 if (queue.isEmpty()) { System.out.println(m * n); return; } int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!queue.isEmpty()) { int[] cur queue.poll(); int x cur[0]; int y cur[1]; for (int[] d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 || nx m || ny 0 || ny n) continue; // 只有0会被同化2是障碍1已经访问过 if (grid[nx][ny] 0) { grid[nx][ny] 1; queue.offer(new int[]{nx, ny}); } } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) ans; } } System.out.println(ans); } }注意一个细节BFS过程中把0改成1必须发生在入队之前不能在出队时才改。否则同一个格子可能被多个邻居重复入队虽然最终结果可能一样但队列会出现大量冗余最坏情况下会拖慢运行时间。3.2 Python用collections.deque别用list当队列Python写这道题最容易踩的坑是用 list 模拟队列然后 pop(0) 出队。pop(0) 的时间复杂度是 O(n)每次出队都要把后面所有元素往前挪数据量一大就卡死。正确做法是使用 collections.deque它的 popleft() 是 O(1)。完整实现from collections import deque def main(): m, n map(int, input().split()) grid [] q deque() for i in range(m): row list(map(int, input().split())) grid.append(row) for j, v in enumerate(row): if v 1: q.append((i, j)) if not q: print(m * n) return dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: x, y q.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 0: grid[nx][ny] 1 q.append((nx, ny)) ans sum(1 for row in grid for v in row if v ! 1) print(ans) if __name__ __main__: main()Python的元组解构和列表推导式让代码很简洁但越界检查不能省。我见过有人把四个方向检查写成一个 if 表达式反而降低了可读性。在机考这种时间紧张的场景下按部就班写最好。另外如果输入里某一行是空字符串用 input().split() 会得到空列表虽然这道题不太会出现这种状况但遇到多行矩阵时最好对行数据做一下空值判断。3.3 JavaScript手写双指针队列避免shift()的O(n)JavaScript 刷算法题时最让人难受的是没有标准库队列。很多人直接用数组的 push 和 shift 模拟小数据没问题但 shift 的时间复杂度是 O(n)会让BFS整体退化。我推荐用双指针法用一个数组当队列head指针指向队首tail指针指向下一个入队位置。出队时只需要 head数组不真的移除元素。因为每个格子最多入队一次数组长度是有限的所以不用担心里面有“废弃”元素占用空间最后统一统计时也不受影响。完整实现const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, line lines.push(line.trim())); rl.on(close, () { const [m, n] lines[0].split(/\s/).map(Number); const grid []; const queue []; let head 0; for (let i 1; i m; i) { const row lines[i].split(/\s/).map(Number); grid.push(row); row.forEach((v, j) { if (v 1) queue.push([i - 1, j]); }); } if (queue.length 0) { console.log(m * n); return; } const dirs [[-1, 0], [1, 0], [0, -1], [0, 1]]; while (head queue.length) { const [x, y] queue[head]; head; for (const [dx, dy] of dirs) { const nx x dx; const ny y dy; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) { grid[nx][ny] 1; queue.push([nx, ny]); } } } let ans 0; for (let i 0; i m; i) { for (let j 0; j n; j) { if (grid[i][j] ! 1) ans; } } console.log(ans); });这里用 while (head queue.length) 判断队列是否为空很巧妙地避开了“队列空了还要手动维护一个size变量”的问题。入队操作只是 pushqueue.length 会增长而head只增不减所以循环终止条件就是队列已经全部处理完。3.4 Cpairint,int queue代码最清爽C写BFS最舒服的地方在于标准库有 queue而且能用 pairint,int 直接存坐标代码读起来很直观。唯一要注意的是C历遍方向数组时最好把方向定义成 int dirs[4][2]然后用 for (auto d : dirs) 的方式遍历比手写四个重复分支干净得多。完整实现#include bits/stdc.h using namespace std; int main() { int m, n; cin m n; vectorvectorint grid(m, vectorint(n)); queuepairint, int q; for (int i 0; i m; i) { for (int j 0; j n; j) { cin grid[i][j]; if (grid[i][j] 1) { q.push({i, j}); } } } if (q.empty()) { cout m * n endl; return 0; } int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) { grid[nx][ny] 1; q.push({nx, ny}); } } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) ans; } } cout ans endl; return 0; }C的 auto [x, y] q.front() 是C17的结构化绑定如果刷题网站用的编译器比较老可能不支持C17。遇到这种情况改成 int x q.front().first; int y q.front().second; 就可以了。机考环境中优先保证代码能被编译而不是追求语法新特性。3.5 C手写结构体数组或双数组队列C语言没有现成的队列容器需要手写。最朴素的做法是用两个全局数组分别存行和列再用 head 和 tail 维护队列。这个方案最简单也最容易记忆。如果觉得不好理解也可以定义一个结构体 Point用 Point 数组做循环队列效果一样。完整实现#include stdio.h #define MAXN 505 int grid[MAXN][MAXN]; int qx[MAXN * MAXN]; int qy[MAXN * MAXN]; int main() { int m, n; scanf(%d %d, m, n); int head 0, tail 0; for (int i 0; i m; i) { for (int j 0; j n; j) { scanf(%d, grid[i][j]); if (grid[i][j] 1) { qx[tail] i; qy[tail] j; } } } if (tail 0) { printf(%d\n, m * n); return 0; } int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (head tail) { int x qx[head]; int y qy[head]; for (int k 0; k 4; k) { int nx x dirs[k][0]; int ny y dirs[k][1]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) { grid[nx][ny] 1; qx[tail] nx; qy[tail] ny; } } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) ans; } } printf(%d\n, ans); return 0; }定义 qx 和 qy 两个数组比定义一个结构体数组省内存也少写一些语法。MAXN 的取值要看题目范围一般机考矩阵边长不会超过500所以505足够。如果你不确定就开成 1005宁可多开一点也不要越界。4. 真正丢分的易错点与自测用例清单4.1 方向数组和越界检查老生常谈但每次都有人错上下左右四个方向看起来简单但漏掉方向是常见错误。我建议把方向数组固定写成 {{-1,0},{1,0},{0,-1},{0,1}}别临时手写个 for 循环四个 if那样特别容易漏。越界检查一定要放在访问 grid[nx][ny] 之前。有些同学喜欢先读 grid[nx][ny] 再判断是否越界这在部分语言里会直接报数组下标越界在C和C里更是未定义行为可能不会立刻崩溃但结果完全不可控。顺序永远是先算新坐标再检查范围最后访问数组。4.2 队列空了再统计顺序不能反BFS结束后最后统计非1元素个数的遍历必不可少。容易错的地方是有人在BFS进行中就去统计“还剩多少个0”然后发现数字一会变一会变最后干脆写错。正确的节奏是初始化时先收集所有1到队列BFS把所有能感染的0都标记成1队列清空后再完整遍历一遍矩阵统计答案。整个过程是“收集起点 - 扩散 - 统计”三步分开。如果你把统计逻辑混进BFS循环里不仅代码难看还容易在边角处出错。4.3 原地修改矩阵的副作用与收益这道题完全可以在原矩阵上直接修改把0改成1。这么做的好处是省空间坏处是改了之后如果后面还想要原始矩阵做别的计算就得提前拷贝一份。对于机考题绝大多数时候原地修改就够了。但有一个陷阱如果你的统计目标是“矩阵中非1的元素个数”那么在原地修改后所有被同化的0已经变成1最后统计时不会把它们计入答案这个逻辑是对的。可如果你最后统计的是“剩余0的个数”就要额外处理2所以统一用 “不等于1” 判断最稳妥它天然包含了0和2两种非1元素。4.4 自测用例与预期输出我整理了一组自测用例机考前拿这组数据过一遍代码基本能覆盖所有易错点。输入矩阵预期输出说明3x3全09无同化源全是非13x3全10所有元素都是13x31 0 0 / 0 0 0 / 0 0 10两个源最终覆盖全图3x31 1 0 / 2 0 0 / 0 0 002无法被同化但其余0全部可达3x32 2 2 / 2 0 2 / 2 2 11中心的0被2完全包围1无法到达2x21 2 / 2 020被2与1隔开无法同化第5个用例特别值得注意四个方向都是2“围墙”把0围死了1就算再多轮也感染不进去。这个用例一跑就能验证你的BFS是否真的把2当成了障碍。5. 从这道题看华为OD机考的实战备考细节5.1 难度定位与分值策略这道题在C卷里属于经典的BFS入门题难度不算高但出现的频率很高。它考察的是最基础的矩阵遍历、队列使用、边界条件处理。如果你连这道题都需要想很久说明BFS还不熟建议先把“岛屿数量”“矩阵扩散”这类基础题刷熟再继续。机考通常有多个题目分值不同。这种中等偏简单的题往往是基础分先把这类题做对再冲后面的难题比死磕一道大题更划算。我的习惯是每题先花5分钟读题如果3分钟之内没有明确思路就先跳过做下一题最后再回头补。因为机考时间有限把能拿的分先拿到手比什么都重要。另外提醒一句机考环境通常要求开双机位正面和侧面各一个摄像头。调试代码的时候要注意屏幕不要被遮挡也不要在电脑背面贴什么标记按考场规则来就行。平时练习时把输入输出习惯都固定好考场上就能少想一些无关的事。5.2 考场上的多语言选择建议很多人纠结用Java还是Python还是C。我的建议很简单用你平时练习最熟的那门语言而不是“哪门语言看起来更高级”。如果你C最熟就用C标准库的queue直接帮你处理队列。如果你Java最熟就用JavaArrayDeque完全够用。如果你最熟Python就用Python虽然Python的运行速度偏慢但这类BFS图的规模通常不大只要用deque效率完全扛得住。真正需要担心的不是语言本身的性能而是你对该语言的输入输出是否闭着眼睛都能写。机考时最崩溃的瞬间不是算法不会而是Scanner或者cin的写法卡壳。所以备考时要固定一套输入输出模板每次练习都从模板开始形成肌肉记忆。5.3 同类型的“兄弟题”清单刷透这一题之后建议把下面几个题型也顺手过一遍它们的核心都是BFS/DFS岛屿数量统计矩阵中连通的1块有多少个是DFS最经典练手题。矩阵扩散给定一个起点求扩散到整个矩阵需要多少轮通常用带层级的BFS。腐烂的橘子多源BFS每分钟腐败橘子感染周围的新鲜橘子求全部腐烂所需时间。迷宫最短路径在带障碍的矩阵中求起点到终点的最短步数核心同样是BFS。这些题本质上都是“矩阵 连通块 扩散”的变体。你把“返回矩阵中非1的元素个数”吃透再往外延伸时会发现套路高度相似初始化队列、方向数组、边界检查、访问标记一套组合拳走天下。我自己刷这道题的时候第一版是用递归DFS写的结果在全0矩阵上直接栈溢出被测试数据教做人了。后来改成多源BFS不仅通过而且代码长度还短了一大截。所以最后再分享一个个人习惯凡是看到“同化”“扩散”“感染”这些词我在草稿纸上第一步就画一个四方向的十字箭头然后问自己“队列里初始放谁”答案就是所有1。把这个条件反射建立起来这类题就再也难不住你了。 华为OD机考数值同化题：多源BFS求矩阵非1元素个数
准备华为OD机考的朋友或者正在刷C卷题库的同学应该对这道“返回矩阵中非1的元素个数”不陌生。它经常以“数值同化”的名字出现在题库里一个二维矩阵有些位置是1有些位置是01会像水波一样向上下左右扩散把碰到的0同化成1最后问整个矩阵中还剩下多少个元素不是1。这道题难度不大套路却非常典型属于“会者不难难者不会”的代表。本文就把它彻底拆开用Java、Python、JS、C、C五种语言各写一版完整题解并且把我自己在刷题和实际机考准备过程中踩过的坑一起列出来。1. 题面还原与样例推演先锁定“同化”的传播规则1.1 题面到底长什么样先说题面。这不是一道需要读半天的题但“数值同化”这四个字确实容易让人想偏。常见描述是这样的给定一个 m 行 n 列的矩阵矩阵中的每个格子取值为0、1、2。其中1表示“同化源”每一轮同化源会将它上下左右四个方向相邻的0变成12表示障碍物1不能同化2。经过足够多轮直到整个矩阵不再发生变化请返回矩阵中非1元素的个数也就是最终值为0或2的格子数量。请注意返回的是“最终矩阵里不等于1的元素个数”不是问“一共同化了多少个格子”也不是问“需要几轮同化完成”。有些同学一上来就开始数初始矩阵里有多少个0那就是把“同化前”和“同化后”搞混了。“数值同化”这个叫法在华为OD机考C卷的题库里经常和“返回矩阵中非1的元素个数”并列出现。我个人理解“同化”两个字强调的就是传播过程1是源头0是被传染目标2是围墙。理解了这一点后面所有代码都是围绕“从所有1出发沿四方向感染相邻0”来写。1.2 手推样例为什么不是一次性扩散用一个3行3列的矩阵来推一遍。输入3 3 1 0 0 0 0 0 0 0 1这一步很多第一次做这道题的同学会算错。有人觉得上下左右四个方向“一步到位”直接把两个1周围的所有0全部变成1然后数一数还有没有0。按照这个错误思路第一轮后矩阵会变成1 1 0 1 0 1 0 1 1看起来剩一个0。但这不是真正的同化过程因为同化是每轮只向相邻格子走一格。真正的过程是这样的第1轮左上角的1感染0,1和1,0右下角的1感染1,2和2,1。第2轮中心1,1被0,1、1,0、1,2、2,1任意一个感染同时0,2被0,1感染2,0被1,0感染。第3轮以后不再变化矩阵全部变成1。最终矩阵里没有非1元素答案是0。能看到同化是按层扩散的“数值”一层一层往外“同化”这就是标准的BFS层级传播。如果直接用“一步到位”的思维去写代码要么多算要么少算。1.3 最容易忽略的两个边界场景边界场景一整个矩阵没有1。这时没有同化源矩阵会发生任何变化吗不会。所以所有格子都是非1元素答案就是 m 乘以 n。边界场景二矩阵中有1同时有2。比如3 3 1 1 0 2 0 0 0 0 0左上角的两个1会把0,2、1,1、2,0都感染成1然后继续往下扩散。但1,0位置的2是墙它挡住了左侧这一列仔细看其实2下面还有2,02,0会被1,1或2,1感染不一定非要穿过2。所以只有被2完全隔开、四周又没有任何1能间接到达的0区域才会永远保持为0。这种情况在真题里出现过读题时别默认矩阵里只有0和1。2. 为什么首选多源BFS从“感染扩散”看算法选型2.1 模拟逐轮扩散的问题看到“每一轮向上下左右扩散”这个描述第一反应是写一个while循环每轮扫描全矩阵把0变成1直到某一轮没有发生任何变化。这个思路本身没错但有个致命问题效率低。假设矩阵是1000乘1000同化传播要1000轮才能结束每一轮都扫描全部100万个格子总共就是10亿次操作。在机考环境下这个复杂度很可能超时。更关键的是逐轮模拟还必须小心处理“同一轮内已经被改成1的格子是否参与本轮扩散”这种边界问题很容易写错。所以这道题的标准解法不是逐轮模拟而是把初始所有1一次性入队做多源BFS。BFS天然自带“层级”属性队列弹出的顺序就是感染顺序不需要额外记录轮次。2.2 多源BFS的两阶段初始化队列 逐层扩展多源BFS和普通BFS的唯一区别就是起始时队列里不是只有一个点而是所有满足条件的点一起进去。这道题里所有初始值为1的格子都是起点。第一阶段读入矩阵的同时把值为1的坐标全部加入队列。第二阶段从队列中逐个取出坐标检查上下左右四个邻居如果邻居是0就把它改成1并加入队列如果邻居是2或者已经变成1就跳过。为什么改成1之后要立刻入队因为BFS的核心是“每个节点只入队一次”。把0改成1相当于给这个格子打上了“已访问”标记既防止它被其他源重复处理又保证它作为新的传播源继续感染后面的格子。如果只标记不入队同化链条就会断掉。用一个生活化类比把多个水龙头放在一个满是干泥土的网格里水从每个水龙头同时向四周渗透遇到石头2就绕开已经湿掉的土地不会再次变干。多源BFS就是同时打开所有水龙头水位边界的扩张顺序就是BFS的队列顺序。2.3 DFS能不能做能用但有代价有同学会问这种连通区域题不是可以用DFS吗确实可以。对于没有障碍的版本DFS递归遍历所有0也能统计出结果。但DFS在矩阵题里有两个隐患第一递归深度风险。如果矩阵是1000乘1000一条路径可能递归几百上千层Java和Python默认栈深度很可能扛不住直接栈溢出。第二DFS的“深度优先”性质和“同化逐层扩散”的直觉不一致排查逻辑错误时更费劲。所以我的建议是矩阵连通类题目只要题目描述里出现“向四周扩散”“感染”“同化”“最短步数”这些字眼优先写BFS。这道题也不例外。3. 五种语言的完整实现与差异点3.1 Java队列用ArrayDeque比LinkedList更稳Java里最常见的队列写法是 LinkedList但在算法题里我更推荐 ArrayDeque。两者的区别在于ArrayDeque基于循环数组实现入队出队都是常数时间而且不会产生LinkedList那种大量小对象的分配开销。这道题的队列里存的是坐标用 int[] 数组存即可。完整实现import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); int[][] grid new int[m][n]; Queueint[] queue new ArrayDeque(); for (int i 0; i m; i) { for (int j 0; j n; j) { grid[i][j] sc.nextInt(); if (grid[i][j] 1) { queue.offer(new int[]{i, j}); } } } // 整个矩阵没有1不需要同化所有元素都是非1 if (queue.isEmpty()) { System.out.println(m * n); return; } int[][] dirs {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!queue.isEmpty()) { int[] cur queue.poll(); int x cur[0]; int y cur[1]; for (int[] d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 || nx m || ny 0 || ny n) continue; // 只有0会被同化2是障碍1已经访问过 if (grid[nx][ny] 0) { grid[nx][ny] 1; queue.offer(new int[]{nx, ny}); } } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) ans; } } System.out.println(ans); } }注意一个细节BFS过程中把0改成1必须发生在入队之前不能在出队时才改。否则同一个格子可能被多个邻居重复入队虽然最终结果可能一样但队列会出现大量冗余最坏情况下会拖慢运行时间。3.2 Python用collections.deque别用list当队列Python写这道题最容易踩的坑是用 list 模拟队列然后 pop(0) 出队。pop(0) 的时间复杂度是 O(n)每次出队都要把后面所有元素往前挪数据量一大就卡死。正确做法是使用 collections.deque它的 popleft() 是 O(1)。完整实现from collections import deque def main(): m, n map(int, input().split()) grid [] q deque() for i in range(m): row list(map(int, input().split())) grid.append(row) for j, v in enumerate(row): if v 1: q.append((i, j)) if not q: print(m * n) return dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] while q: x, y q.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 0: grid[nx][ny] 1 q.append((nx, ny)) ans sum(1 for row in grid for v in row if v ! 1) print(ans) if __name__ __main__: main()Python的元组解构和列表推导式让代码很简洁但越界检查不能省。我见过有人把四个方向检查写成一个 if 表达式反而降低了可读性。在机考这种时间紧张的场景下按部就班写最好。另外如果输入里某一行是空字符串用 input().split() 会得到空列表虽然这道题不太会出现这种状况但遇到多行矩阵时最好对行数据做一下空值判断。3.3 JavaScript手写双指针队列避免shift()的O(n)JavaScript 刷算法题时最让人难受的是没有标准库队列。很多人直接用数组的 push 和 shift 模拟小数据没问题但 shift 的时间复杂度是 O(n)会让BFS整体退化。我推荐用双指针法用一个数组当队列head指针指向队首tail指针指向下一个入队位置。出队时只需要 head数组不真的移除元素。因为每个格子最多入队一次数组长度是有限的所以不用担心里面有“废弃”元素占用空间最后统一统计时也不受影响。完整实现const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); const lines []; rl.on(line, line lines.push(line.trim())); rl.on(close, () { const [m, n] lines[0].split(/\s/).map(Number); const grid []; const queue []; let head 0; for (let i 1; i m; i) { const row lines[i].split(/\s/).map(Number); grid.push(row); row.forEach((v, j) { if (v 1) queue.push([i - 1, j]); }); } if (queue.length 0) { console.log(m * n); return; } const dirs [[-1, 0], [1, 0], [0, -1], [0, 1]]; while (head queue.length) { const [x, y] queue[head]; head; for (const [dx, dy] of dirs) { const nx x dx; const ny y dy; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) { grid[nx][ny] 1; queue.push([nx, ny]); } } } let ans 0; for (let i 0; i m; i) { for (let j 0; j n; j) { if (grid[i][j] ! 1) ans; } } console.log(ans); });这里用 while (head queue.length) 判断队列是否为空很巧妙地避开了“队列空了还要手动维护一个size变量”的问题。入队操作只是 pushqueue.length 会增长而head只增不减所以循环终止条件就是队列已经全部处理完。3.4 Cpairint,int queue代码最清爽C写BFS最舒服的地方在于标准库有 queue而且能用 pairint,int 直接存坐标代码读起来很直观。唯一要注意的是C历遍方向数组时最好把方向定义成 int dirs[4][2]然后用 for (auto d : dirs) 的方式遍历比手写四个重复分支干净得多。完整实现#include bits/stdc.h using namespace std; int main() { int m, n; cin m n; vectorvectorint grid(m, vectorint(n)); queuepairint, int q; for (int i 0; i m; i) { for (int j 0; j n; j) { cin grid[i][j]; if (grid[i][j] 1) { q.push({i, j}); } } } if (q.empty()) { cout m * n endl; return 0; } int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto d : dirs) { int nx x d[0]; int ny y d[1]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) { grid[nx][ny] 1; q.push({nx, ny}); } } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) ans; } } cout ans endl; return 0; }C的 auto [x, y] q.front() 是C17的结构化绑定如果刷题网站用的编译器比较老可能不支持C17。遇到这种情况改成 int x q.front().first; int y q.front().second; 就可以了。机考环境中优先保证代码能被编译而不是追求语法新特性。3.5 C手写结构体数组或双数组队列C语言没有现成的队列容器需要手写。最朴素的做法是用两个全局数组分别存行和列再用 head 和 tail 维护队列。这个方案最简单也最容易记忆。如果觉得不好理解也可以定义一个结构体 Point用 Point 数组做循环队列效果一样。完整实现#include stdio.h #define MAXN 505 int grid[MAXN][MAXN]; int qx[MAXN * MAXN]; int qy[MAXN * MAXN]; int main() { int m, n; scanf(%d %d, m, n); int head 0, tail 0; for (int i 0; i m; i) { for (int j 0; j n; j) { scanf(%d, grid[i][j]); if (grid[i][j] 1) { qx[tail] i; qy[tail] j; } } } if (tail 0) { printf(%d\n, m * n); return 0; } int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (head tail) { int x qx[head]; int y qy[head]; for (int k 0; k 4; k) { int nx x dirs[k][0]; int ny y dirs[k][1]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 0) { grid[nx][ny] 1; qx[tail] nx; qy[tail] ny; } } } int ans 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) ans; } } printf(%d\n, ans); return 0; }定义 qx 和 qy 两个数组比定义一个结构体数组省内存也少写一些语法。MAXN 的取值要看题目范围一般机考矩阵边长不会超过500所以505足够。如果你不确定就开成 1005宁可多开一点也不要越界。4. 真正丢分的易错点与自测用例清单4.1 方向数组和越界检查老生常谈但每次都有人错上下左右四个方向看起来简单但漏掉方向是常见错误。我建议把方向数组固定写成 {{-1,0},{1,0},{0,-1},{0,1}}别临时手写个 for 循环四个 if那样特别容易漏。越界检查一定要放在访问 grid[nx][ny] 之前。有些同学喜欢先读 grid[nx][ny] 再判断是否越界这在部分语言里会直接报数组下标越界在C和C里更是未定义行为可能不会立刻崩溃但结果完全不可控。顺序永远是先算新坐标再检查范围最后访问数组。4.2 队列空了再统计顺序不能反BFS结束后最后统计非1元素个数的遍历必不可少。容易错的地方是有人在BFS进行中就去统计“还剩多少个0”然后发现数字一会变一会变最后干脆写错。正确的节奏是初始化时先收集所有1到队列BFS把所有能感染的0都标记成1队列清空后再完整遍历一遍矩阵统计答案。整个过程是“收集起点 - 扩散 - 统计”三步分开。如果你把统计逻辑混进BFS循环里不仅代码难看还容易在边角处出错。4.3 原地修改矩阵的副作用与收益这道题完全可以在原矩阵上直接修改把0改成1。这么做的好处是省空间坏处是改了之后如果后面还想要原始矩阵做别的计算就得提前拷贝一份。对于机考题绝大多数时候原地修改就够了。但有一个陷阱如果你的统计目标是“矩阵中非1的元素个数”那么在原地修改后所有被同化的0已经变成1最后统计时不会把它们计入答案这个逻辑是对的。可如果你最后统计的是“剩余0的个数”就要额外处理2所以统一用 “不等于1” 判断最稳妥它天然包含了0和2两种非1元素。4.4 自测用例与预期输出我整理了一组自测用例机考前拿这组数据过一遍代码基本能覆盖所有易错点。输入矩阵预期输出说明3x3全09无同化源全是非13x3全10所有元素都是13x31 0 0 / 0 0 0 / 0 0 10两个源最终覆盖全图3x31 1 0 / 2 0 0 / 0 0 002无法被同化但其余0全部可达3x32 2 2 / 2 0 2 / 2 2 11中心的0被2完全包围1无法到达2x21 2 / 2 020被2与1隔开无法同化第5个用例特别值得注意四个方向都是2“围墙”把0围死了1就算再多轮也感染不进去。这个用例一跑就能验证你的BFS是否真的把2当成了障碍。5. 从这道题看华为OD机考的实战备考细节5.1 难度定位与分值策略这道题在C卷里属于经典的BFS入门题难度不算高但出现的频率很高。它考察的是最基础的矩阵遍历、队列使用、边界条件处理。如果你连这道题都需要想很久说明BFS还不熟建议先把“岛屿数量”“矩阵扩散”这类基础题刷熟再继续。机考通常有多个题目分值不同。这种中等偏简单的题往往是基础分先把这类题做对再冲后面的难题比死磕一道大题更划算。我的习惯是每题先花5分钟读题如果3分钟之内没有明确思路就先跳过做下一题最后再回头补。因为机考时间有限把能拿的分先拿到手比什么都重要。另外提醒一句机考环境通常要求开双机位正面和侧面各一个摄像头。调试代码的时候要注意屏幕不要被遮挡也不要在电脑背面贴什么标记按考场规则来就行。平时练习时把输入输出习惯都固定好考场上就能少想一些无关的事。5.2 考场上的多语言选择建议很多人纠结用Java还是Python还是C。我的建议很简单用你平时练习最熟的那门语言而不是“哪门语言看起来更高级”。如果你C最熟就用C标准库的queue直接帮你处理队列。如果你Java最熟就用JavaArrayDeque完全够用。如果你最熟Python就用Python虽然Python的运行速度偏慢但这类BFS图的规模通常不大只要用deque效率完全扛得住。真正需要担心的不是语言本身的性能而是你对该语言的输入输出是否闭着眼睛都能写。机考时最崩溃的瞬间不是算法不会而是Scanner或者cin的写法卡壳。所以备考时要固定一套输入输出模板每次练习都从模板开始形成肌肉记忆。5.3 同类型的“兄弟题”清单刷透这一题之后建议把下面几个题型也顺手过一遍它们的核心都是BFS/DFS岛屿数量统计矩阵中连通的1块有多少个是DFS最经典练手题。矩阵扩散给定一个起点求扩散到整个矩阵需要多少轮通常用带层级的BFS。腐烂的橘子多源BFS每分钟腐败橘子感染周围的新鲜橘子求全部腐烂所需时间。迷宫最短路径在带障碍的矩阵中求起点到终点的最短步数核心同样是BFS。这些题本质上都是“矩阵 连通块 扩散”的变体。你把“返回矩阵中非1的元素个数”吃透再往外延伸时会发现套路高度相似初始化队列、方向数组、边界检查、访问标记一套组合拳走天下。我自己刷这道题的时候第一版是用递归DFS写的结果在全0矩阵上直接栈溢出被测试数据教做人了。后来改成多源BFS不仅通过而且代码长度还短了一大截。所以最后再分享一个个人习惯凡是看到“同化”“扩散”“感染”这些词我在草稿纸上第一步就画一个四方向的十字箭头然后问自己“队列里初始放谁”答案就是所有1。把这个条件反射建立起来这类题就再也难不住你了。