华为OD机考矩阵同化题：非1元素计数与连通区域DFS五种语言实现

华为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 += 1

2.2 第二问：DFS、BFS、并查集到底选哪个

处理连通区域有三条路：深度优先搜索 DFS、广度优先搜索 BFS、并查集 Union-Find。我做过一个对比，直接说结论：

为什么推荐显式栈 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-4=8。数值 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++; ArrayDeque<int[]> 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 JavaScript：Node 环境的 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; vector<vector<int>> grid(m, vector<int>(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"; vector<vector<bool>> visited(m, vector<bool>(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++; stack<pair<int, int>> st; st.push({i, j}); visited[i][j] = true; int val = grid[i][j]; while (!st.empty()) { pair<int, 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++ 写这个题有两个优势，一是vector<vector<int>>可以动态开，不用在编译期定死大小，二是 STL 的stack直接用。注意开头两行ios::sync_with_stdio(false); cin.tie(nullptr);一定要写，否则大数据量下cin可能比scanf慢不少。有些考场的老版本编译器不支持 C++17 的结构化绑定auto [x, y] = cur，所以我这里故意写成pair<int,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 边界测试用例设计技巧

这些用例你可以在本地全部跑一遍，再上机就心里有底了。特别是 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 跨语言差异速查表

这张表建议截图存手机里，考前看一眼，比翻几百页面经有用。

5.4 一个容易被忽略的细节：输出要不要带前缀

我在刷题群里见过有人栽在这个细节上。有些题明确要求只输出数字，有些题输出non-one count: 8这种带说明的格式，判题系统两者都接受的情况也存在，但完全判错的情况也存在。最保险的办法是仔细读题面的“输出描述”，按它的原样来。如果题目只说“输出结果”，那默认只输出数字。我平时练习就按带不带前缀两种格式都测一遍，上机时就不会因为这个丢分。

最后分享一点个人经验

我备考那会，把这题在五种语言里都跑了一遍，最后总结出一个固定套路：先背读取矩阵的模板，再背显式栈 DFS 模板，最后背边界用例集。考场上看到矩阵类题目，我根本不经过大脑，直接套模板，时间全留给真正需要思考的难题。这道题本身难度不高，但它很适合当“模板题”来练，因为矩阵读取、方向数组、visited 标记、区域计数这些能力，在 OD 机考里几乎每个题目都能用上。把这题吃透，你的矩阵类算法水平已经超过大多数备考的人了。