华为OD机考C卷里有一类题看着像送分题给你一个矩阵数一数里面有多少个元素不是1再配合一个“数值同化”的处理。可真正坐到双机位摄像头下面输入输出的格式、边界条件、递归深度处处都是翻车点。今天我把这道高频题完整拆一遍从题意理解到 Java、Python、JS、C、C 五种写法全部给出可直接照抄的实现并把我备考时踩过的坑一并说出来。这篇文章适合正在刷OD机试题的考生也适合想让基础算法更扎实的初学者看完你能直接把这题的模板背下来。1. 题目到底在考什么拆开“非1”和“同化”两个关键词1.1 “返回矩阵中非1的元素个数”就是送分部分题目给的矩阵一般是 m 行 n 列元素是整数。最常见的设定里数字 1 代表障碍、墙体或者不能参与计算的位置其余的数字比如 0、2、3 都可以随便走或者需要被统计。第一问“返回非1元素个数”本质上就是问你矩阵里有多少个格子不等于 1。这个部分没有任何算法含量两层循环扫一遍遇到不等于1的格子就计数器加一时间复杂度 O(m*n)空间复杂度 O(1)。我在模拟考时见过很多人在这题上翻车不是不会数数而是把输入读错了、行列搞反了、或者把 1 当成“要统计的数量”理解错了。送分题能不能稳稳拿住直接决定了整场考试的信心。1.2 “数值同化”到底是什么意思这是整道题最容易引起恐慌的词。我第一次见到“同化”两个字也愣了半天后来刷多了才发现它在绝大多数题里就是“连通区域”的另一种说法。通俗点讲矩阵里相邻上下左右四个方向并且数值相同的格子会被“同化”成一个整体。就像一个油漆桶工具你把鼠标点在一个颜色区域里所有相连的同色格子会被一起填色一个连通块只算一次。所以这道题的第二问最常见的形式就是把非1且数值相同的连通区域合并后统计一共分成多少个区域。也可能变成“从某个起点开始同化问最终矩阵里有几个非1元素”但无论如何核心算法都是遍历连通分量。理解了这一点题目就从“不明觉厉”变成了“套模板”。1.3 命题人真正想考察的三件事这道题表面考矩阵遍历实际考的是三项硬功夫。第一项是 ACM 模式的输入输出处理。OD 机考不是力扣那种只写核心函数的环境你得自己写 main、自己解析 stdin读错一个空格就全盘皆输。第二项是 DFS/BFS 的基本功尤其是把递归改成显式栈的意识因为大矩阵下递归深度等于格子总数很容易爆栈。第三项是边界条件处理比如全 1 矩阵、单元素矩阵、全是 0 的矩阵这些用例能一次性过滤掉一大半错误实现。2. 核心算法思路与方案选型2.1 第一问别想太多直接遍历统计非 1 元素的个数最朴素的写法就是嵌套循环。这个解法已经是最优的因为任何解法都要把矩阵过一遍才能知道每个格子是什么值。别在送分题上炫技什么并行、什么前缀和都不需要。count 0 for i in range(m): for j in range(n): if grid[i][j] ! 1: count 12.2 第二问DFS、BFS、并查集到底选哪个处理连通区域有三条路深度优先搜索 DFS、广度优先搜索 BFS、并查集 Union-Find。我做过一个对比直接说结论方案代码量爆栈风险调试难度我的推荐度递归 DFS最少高大矩阵直接崩低不推荐上机使用显式栈 DFS中等无低最推荐队列 BFS中等无低可以并查集较多无中不推荐为什么推荐显式栈 DFS因为递归 DFS 在 1000*1000 的矩阵里递归深度可能达到一百万层绝大多数编程环境的函数调用栈直接溢出。而显式栈用数组或者容器模拟想开多大开多大。并查集虽然不会爆栈但二维坐标要映射成一维下标写起来啰嗦在紧张的机考环境下没必要给自己加戏。BFS 也很好但队列操作比栈稍重一点点两者本质没有差距你熟哪个用哪个。2.3 复杂度分析为什么这个方案稳过无论用 DFS 还是 BFS每个格子最多入栈一次、出栈一次所以时间复杂度和第一问一样是 O(mn)。额外空间主要是 visited 标记数组 O(mn) 和栈空间最坏情况下栈里同时放所有格子也是 O(mn)。对于机考常见的 10001000 规模这个复杂度完全在安全线内。有一点要特别注意visited 标记的时机。正确做法是“入栈前立刻标记”而不是“出栈时再标记”。出栈时标记会导致同一个格子被多个邻居重复入栈虽然结果可能对但摊还复杂度会退化数据一大就超时。这是我在代码里特别加注释的原因。3. 五种语言完整实现与逐行解读下面统一用这个样例来验证代码3 4 0 1 1 2 0 0 1 2 3 3 3 1期望输出non-one count: 8 regions: 3解释一下矩阵里 1 有 4 个所以非1是 12-48。数值 0 的连通块在左上角数值 2 的连通块在右上角数值 3 的连通块在左下角一共 3 个区域。3.1 Java用栈代替递归注意泛型写法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]; for (int i 0; i m; i) { for (int j 0; j n; j) { grid[i][j] sc.nextInt(); } } int nonOne 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) { nonOne; } } } System.out.println(non-one count: nonOne); boolean[][] visited new boolean[m][n]; int[] dx {-1, 1, 0, 0}; int[] dy {0, 0, -1, 1}; int regions 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (!visited[i][j] grid[i][j] ! 1) { regions; ArrayDequeint[] stack new ArrayDeque(); stack.push(new int[]{i, j}); visited[i][j] true; int val grid[i][j]; while (!stack.isEmpty()) { int[] cur stack.pop(); int x cur[0], y cur[1]; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] val grid[nx][ny] ! 1) { visited[nx][ny] true; stack.push(new int[]{nx, ny}); } } } } } } System.out.println(regions: regions); } }Java 有几个点值得说。第一ArrayDeque当栈用push 和 pop 都很快比Stack类更推荐。第二这里比较基准是val也就是每个连通块起点格子的值。因为同化的定义是“从起点出发把相邻且相等的值合并”所以以起点值为准如果你更喜欢“当前格子值”作为基准效果一样因为同一连通块内相邻值必然相等可以传递。第三visited[i][j] true必须在push之前就执行这一点所有语言都一样。3.2 Python一次性读入最省时间显式栈防递归爆栈import sys def main(): data sys.stdin.read().strip().split() if not data: return m, n int(data[0]), int(data[1]) grid [] idx 2 for _ in range(m): row [] for _ in range(n): row.append(int(data[idx])) idx 1 grid.append(row) non_one 0 for i in range(m): for j in range(n): if grid[i][j] ! 1: non_one 1 print(non-one count:, non_one) visited [[False] * n for _ in range(m)] dx [-1, 1, 0, 0] dy [0, 0, -1, 1] regions 0 for i in range(m): for j in range(n): if not visited[i][j] and grid[i][j] ! 1: regions 1 stack [(i, j)] visited[i][j] True val grid[i][j] while stack: x, y stack.pop() for k in range(4): nx x dx[k] ny y dy[k] if 0 nx m and 0 ny n \ and not visited[nx][ny] \ and grid[nx][ny] val \ and grid[nx][ny] ! 1: visited[nx][ny] True stack.append((nx, ny)) print(regions:, regions) if __name__ __main__: main()Python 最容易踩的坑是input()逐行读太慢数据量大时可能 TLE所以我直接用sys.stdin.read()一次性读进来再按空白字符切分。另一个坑是递归 DFS就算你写了sys.setrecursionlimit(1000000)在 Python 解释器里深递归依然可能崩而且性能很差。显式栈是最省心的写法。还有一个小细节visited不要写成[[False] * n] * m内层列表会共用引用改一个全变这是 Python 新手最常见的隐形 bug。3.3 JavaScriptNode 环境的 readline 读入要小心异步const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { const data []; for (const line of lines) { const parts line.split(/\s/).map(Number); data.push(...parts); } if (data.length 2) return; const m data[0], n data[1]; const grid []; let idx 2; for (let i 0; i m; i) { grid.push(data.slice(idx, idx n)); idx n; } let nonOne 0; for (let i 0; i m; i) { for (let j 0; j n; j) { if (grid[i][j] ! 1) nonOne; } } console.log(non-one count:, nonOne); const visited Array.from({ length: m }, () Array(n).fill(false)); const dx [-1, 1, 0, 0]; const dy [0, 0, -1, 1]; let regions 0; for (let i 0; i m; i) { for (let j 0; j n; j) { if (!visited[i][j] grid[i][j] ! 1) { regions; const stack [[i, j]]; visited[i][j] true; const val grid[i][j]; while (stack.length) { const [x, y] stack.pop(); for (let k 0; k 4; k) { const nx x dx[k]; const ny y dy[k]; if (nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] val grid[nx][ny] ! 1) { visited[nx][ny] true; stack.push([nx, ny]); } } } } } } console.log(regions:, regions); });JS 里最常见的问题是很多人习惯直接fs.readFileSync(/dev/stdin, utf-8)这在本地 Linux 没问题但 OD 机考的在线编辑器不保证路径可用所以最稳妥还是用readline的line事件把输入收齐在close里统一处理。另一个容易错的地方是Array.from({ length: m }, () Array(n).fill(false))这一步不能省Array(n).fill(Array(m).fill(false))会共享引用。还有split(/\s/)比split( )更抗压能同时处理空格和换行混合的情况。3.4 C快读快写加 pair 栈稳字当头#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin m n; vectorvectorint grid(m, vectorint(n)); for (int i 0; i m; i) { for (int j 0; j n; j) { cin grid[i][j]; } } int nonOne 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) nonOne; } } cout non-one count: nonOne \n; vectorvectorbool visited(m, vectorbool(n, false)); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int regions 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (!visited[i][j] grid[i][j] ! 1) { regions; stackpairint, int st; st.push({i, j}); visited[i][j] true; int val grid[i][j]; while (!st.empty()) { pairint, int cur st.top(); st.pop(); int x cur.first, y cur.second; for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] val grid[nx][ny] ! 1) { visited[nx][ny] true; st.push({nx, ny}); } } } } } } cout regions: regions \n; return 0; }C 写这个题有两个优势一是vectorvectorint可以动态开不用在编译期定死大小二是 STL 的stack直接用。注意开头两行ios::sync_with_stdio(false); cin.tie(nullptr);一定要写否则大数据量下cin可能比scanf慢不少。有些考场的老版本编译器不支持 C17 的结构化绑定auto [x, y] cur所以我这里故意写成pairint,int cur再取 first 和 second兼容性拉满。3.5 C 语言手动栈 全局数组最朴素也最可控#include stdio.h #include stdbool.h #include string.h #define MAXN 1005 int grid[MAXN][MAXN]; bool visited[MAXN][MAXN]; typedef struct { int x, y; } Point; int main() { int m, n; if (scanf(%d %d, m, n) ! 2) { return 0; } for (int i 0; i m; i) { for (int j 0; j n; j) { scanf(%d, grid[i][j]); } } int nonOne 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] ! 1) { nonOne; } } } printf(non-one count: %d\n, nonOne); memset(visited, 0, sizeof(visited)); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; Point stack[MAXN * MAXN]; int top -1; int regions 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (!visited[i][j] grid[i][j] ! 1) { regions; top -1; stack[top] (Point){i, j}; visited[i][j] true; int val grid[i][j]; while (top 0) { Point cur stack[top--]; for (int k 0; k 4; k) { int nx cur.x dx[k]; int ny cur.y dy[k]; if (nx 0 nx m ny 0 ny n !visited[nx][ny] grid[nx][ny] val grid[nx][ny] ! 1) { visited[nx][ny] true; stack[top] (Point){nx, ny}; } } } } } } printf(regions: %d\n, regions); return 0; }C 语言没有现成的栈所以用一个一维数组模拟top指向栈顶。我把grid和visited都开成全局数组原因很简单全局区空间大放在main里的局部大数组可能直接触发栈溢出。MAXN取 1005 是为了兼容 1000*1000 的矩阵如果题目说数据范围更大就把这个宏改大或者改造成动态分配。memset重置二维布尔数组在 C 里非常快比双重循环赋值更省事。3.6 同一逻辑五种语言差异在哪把五份代码放在一起看核心逻辑完全一致读入矩阵、遍历计数、显式栈做连通区域统计。差别只在语法层。Java 和 C 的容器是现成的但要注意泛型和版本兼容Python 最简洁但必须防递归爆栈和列表引用共享JS 要看懂异步读入把逻辑全部放进close回调里C 语言最自由但空间和时间都要自己控制。机考时选你最熟的语言把这些模板背下来能省出大量时间。4. 机考现场双机位环境与备考节奏4.1 双机位考试怎么准备OD 机考采用双机位监考第一机位是电脑摄像头正对脸部和屏幕第二机位一般是手机放在侧后方 45 度左右要能拍到你的手和电脑屏幕。开考前一定要提前调试设备光线太暗会导致人脸识别不通过摄像头被遮挡直接无法进入考试。手机记得关掉所有通知开启免打扰最好飞行模式后连 WiFi防止考试中途有电话打进来被判异常。桌面上不要放手机、笔记本、纸质资料只留证件和最基本的文具摄像头能看到的位置都要干净。双机位监考这几年查得很严我自己见过有考生因为低头看键盘时间太久被弹窗提醒多次提醒可能直接终止考试。所以备考阶段就不要养成“盯着键盘找键位”的习惯尽量盲打。4.2 读题、编码、自测的节奏控制我的建议是拿到题先花 3 分钟把题意完全读清楚尤其是“同化”这种奇怪词确认到底输出什么。别急着写先想明白问的是“非1个数”还是“连通区域数”两个都要输出就都写上。然后先写第一问暴力遍历白送的分拿到手。第二问直接用背好的显式栈 DFS 模板一气呵成。写完不要立刻交卷先跑题目给的样例再自己补三个边界用例全 1、全 0、单个元素。这三类用例能暴露 90% 的问题。最后检查输出格式是只要数字还是要带字符串。OD 机考的判题系统通常比较宽容但输出格式错了照样零分。4.3 边界测试用例设计技巧测试输入期望结果测试目的1 1加一个1non-one 0, regions 0全是障碍1 1加一个0non-one 1, regions 1单元素可走1 3加0 0 0non-one 3, regions 1一整行连成一块2 3加0 1 0 / 0 1 0non-one 4, regions 2被障碍隔开3 4上面的标准样例non-one 8, regions 3常规多区域这些用例你可以在本地全部跑一遍再上机就心里有底了。特别是 regions 的计数很多错误代码在只有一个连通块时碰巧对一旦出现多个区域就多算或少算所以“被障碍隔开的多个区域”是必测的。5. 常见问题与排查技巧实录5.1 输出结果不对先按这个顺序排查第一确认输入解析。打印一下 m 和 n再看 grid 的第一行很多时候是行列搞反了或者数据读串行。第二确认 visited 标记时机。如果标记写在pop之后会出现同一个格子多次入栈虽然结果可能对但逻辑已有隐患。第三确认比较基准。如果是“同化”题必须以起点值 val 为基准如果基准写成grid[x][y]也要能推导出等价别写成遍历到一半再改。第四确认计数位置。regions必须放在外层发现“未访问且非1”格子的地方一次连通块只能加一次放错位置会整个测试点全挂。我排查过很多次最常见的就是这三类问题。5.2 超时和爆栈的应急预案如果第一版代码用递归 DFS 超时或者直接崩了不要犹豫立刻改成显式栈。递归转栈其实很简单递归函数里的“当前参数”就是栈里存的坐标每次要递归就压栈循环处理直到栈空。这个转换要练成肌肉记忆考场上根本没时间现场想。Python 的话还有一个优化点把visited合并进矩阵本身直接把访问过的非1格子改成 1省掉一个二维数组。这样内存更小速度也更快但要注意别把原始数据改掉影响后续判断。如果是 C确认是否写了ios::sync_with_stdio(false)没写的话大数据量下cin可能成为瓶颈。5.3 跨语言差异速查表语言输入读取推荐栈写法最容易踩的坑JavaScannerArrayDequeint[]泛型数组写错、忘记先标记 visitedPythonsys.stdin.read().split()list当栈[[False]*n]*m共享引用、递归爆栈JSreadline的line/close普通数组 push/pop同步读文件路径依赖、异步回调忘了收尾Ccin 关同步stackpairint,int结构化绑定导致老编译器报错Cscanf自定义数组栈局部大数组爆栈、忘记memset这张表建议截图存手机里考前看一眼比翻几百页面经有用。5.4 一个容易被忽略的细节输出要不要带前缀我在刷题群里见过有人栽在这个细节上。有些题明确要求只输出数字有些题输出non-one count: 8这种带说明的格式判题系统两者都接受的情况也存在但完全判错的情况也存在。最保险的办法是仔细读题面的“输出描述”按它的原样来。如果题目只说“输出结果”那默认只输出数字。我平时练习就按带不带前缀两种格式都测一遍上机时就不会因为这个丢分。最后分享一点个人经验我备考那会把这题在五种语言里都跑了一遍最后总结出一个固定套路先背读取矩阵的模板再背显式栈 DFS 模板最后背边界用例集。考场上看到矩阵类题目我根本不经过大脑直接套模板时间全留给真正需要思考的难题。这道题本身难度不高但它很适合当“模板题”来练因为矩阵读取、方向数组、visited 标记、区域计数这些能力在 OD 机考里几乎每个题目都能用上。把这题吃透你的矩阵类算法水平已经超过大多数备考的人了。