2025 B卷 200分 题型
本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；
并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；
本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》
华为OD机试真题《矩阵中非1的数量 》：
文章快捷目录
题目描述及说明
Java
python
JavaScript
C++
C
GO
题目名称：矩阵中非1的数量
- 知识点：广度优先搜索（BFS）、矩阵遍历
- 时间限制：1秒
- 空间限制：256MB
- 限定语言：不限
题目描述
存在一个m*n的二维数组，其成员取值范围为0、1、2。其中：
- 值为1的元素具备同化特性，每经过1秒，会将其上下左右相邻的值为0的元素同化为1；
- 值为2的元素免疫同化，不会被改变；
- 初始时，矩阵所有成员随机初始化为0或2，且需将矩阵的[0,0]位置强制修改为1；
- 经过足够长时间后，求矩阵中剩余的非1元素（即0和2）的总数量。
输入描述
前两个数字为矩阵大小m和n，后续为矩阵内容，每行数据用空格分隔。
示例输入：
4 4
0 0 0 0
0 2 2 2
0 2 0 0
0 2 0 0
输出描述
返回非1的元素个数。
示例输出：
9
（解释：最终同化结果为左上角扩散的1和免疫的2，剩余0和2共9个）
Java
问题分析
我们需要找到一个矩阵中经过足够时间后，未被同化为1的元素数量。初始时，矩阵的[0,0]位置被强制设置为1，而1会扩散到相邻的0，但2保持不变。非1元素包括无法被扩散到的0和所有的2。
解题思路
- 初始化矩阵：将
[0,0]位置强制设为1。 - 广度优先搜索（BFS）：从初始的1开始，逐层感染相邻的0。
- 统计结果：遍历矩阵，统计所有未被感染的0和所有2的总数。
代码实现
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt(); // 读取行数
int n = scanner.nextInt(); // 读取列数
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt(); // 填充矩阵
}
}
matrix[0][0] = 1; // 强制将[0,0]设为1
// 初始化队列，并将起始点[0,0]加入队列
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{
0, 0});
// 四个方向的偏移量：上、下、左、右
int[][] dirs = {
{
-1, 0}, {
1, 0}, {
0, -1}, {
0, 1}};
// BFS处理所有可扩散的0
while (!queue.isEmpty()) {
int[] cell = queue.poll(); // 取出当前节点
int x = cell[0], y = cell[1];
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
// 检查新坐标是否合法，且是否为可感染的0
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] == 0) {
matrix[nx][ny] = 1; // 标记为已感染
queue.add(new int[]{
nx, ny}); // 加入队列以便继续扩散
}
}
}
// 统计未被感染的0和所有2的总数
int count = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] != 1) {
// 未被感染的0或2
count++;
}
}
}
System.out.println(count);
}
}
代码解析
读取输入
int m = scanner.nextInt(); int n = scanner.nextInt(); int[][] matrix = new int[m][n];- 读取矩阵的行列数，并初始化二维数组。
强制初始化
matrix[0][0] = 1;- 根据题目要求，无论输入如何，
[0,0]必须为1。
- 根据题目要求，无论输入如何，
BFS初始化
Queue<int[]> queue = new LinkedList<>(); queue.add(new int[]{ 0, 0});- 将起始点
[0,0]加入队列，作为扩散的起点。
- 将起始点
方向偏移量
int[][] dirs = { { -1, 0}, { 1, 0}, { 0, -1}, { 0, 1}};- 定义四个方向的坐标偏移，用于遍历相邻位置。
BFS扩散过程
while (!queue.isEmpty()) { int[] cell = queue.poll(); for (int[] dir : dirs) { int nx = x + dir[0], ny = y + dir[1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] == 0) { matrix[nx][ny] = 1; queue.add(new int[]{ nx, ny}); } } }- 遍历队列中每个节点，检查其四个相邻位置是否可被感染（值为0）。
- 若可感染，将其标记为1，并加入队列继续扩散。
统计未被感染元素
int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] != 1) { count++; } } }- 最终遍历矩阵，统计所有非1元素（未被感染的0和所有2）。
示例测试
示例1输入：
4 4
0 0 0 0
0 2 2 2
0 2 0 0
0 2 0 0
输出：
9
解析：左上角的1扩散感染周围0，但被2阻挡，未感染的0和所有2的总数为9。
示例2输入：
3 3
0 2 0
2 2 0
0 0 0
输出：
8
解析：初始的1无法扩散到其他0，总共有8个非1元素。
示例3输入：
2 2
2 0
0 2
输出：
1
解析：只有右下角的2未被感染。
综合分析
时间复杂度：
O(m*n)- BFS遍历每个节点最多一次，时间复杂度为矩阵元素数量。
空间复杂度：
O(m*n)- 存储矩阵和队列的空间。
正确性保证：
- BFS确保所有可达的0都被感染，剩余的非1元素严格符合题目要求。
优势：
- 高效处理大规模矩阵，避免重复计算。
- 逻辑清晰，易于理解和维护。
适用场景：
- 需要快速计算病毒扩散、网络传播等类似模型的场景。
python
问题分析
我们需要计算矩阵中经过足够时间后未被感染的0和所有2的总数。初始时，矩阵的左上角[0,0]被强制设为1，1会扩散到相邻的0，而2保持不变。通过广度优先搜索（BFS）模拟扩散过程，最终统计剩余的非1元素。
解题思路
- 输入处理：读取矩阵的行列和元素，并将[0,0]强制设为1。
- BFS初始化：将初始点[0,0]加入队列。
- 扩散模拟：逐层扩散，将可达的0标记为1。
- 结果统计：遍历矩阵，统计所有非1元素的数量。
代码实现
import sys