华为OD机试 - 返回矩阵中非1的元素个数 - 广度优先搜索BFS（Python/JS/C/C++ 2024 E卷 200分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

存在一个m*n的二维数组Q，其成员取值范围为0，1，2。

其中值为1的元素具备向四周传染的特性，每经过1s，将上下左右值为0的元素同化为1。

而值为2的元素，免疫同化。

将数组所有成员随机初始化为0或2，再将矩阵的[0, 0]元素修改成1，在经过足够长的时间后求矩阵中有多少个元素是0或2（即0和2数量之和）。

二、输入描述

输入人的前两个数字是矩阵大小。后面是数字矩阵内容。

三、输出描述

返回矩阵中非1的元素个数。

四、测试用例

测试用例1：

1、输入

4 4
0 0 0 0
0 2 2 2
0 2 0 0
0 2 0 0

2、输出

9

3、说明

起始位置 (0, 0) 被修改为 1 后，开始进行感染传播。

感染从 (0, 0) 向四周扩散，传播到与其相邻的上下左右位置：

• 第一行的所有元素 (0, 1)、(0, 2)、(0, 3) 被感染，修改为 1。
• 第二行的 (1, 0) 被感染，修改为 1。
• 第三行的 (2, 0) 被感染，修改为 1。
• 第四行的 (3, 0) 被感染，修改为 1。

感染传播会遇到值为 2 的元素，这些元素免疫感染，因此在接触到值为 2 的位置时停止扩散。

最终矩阵状态：

1 1 1 1
1 2 2 2
1 2 0 0
1 2 0 0

最终矩阵中，所有的 0 和 2 均未被感染。共计有 9 个非 1 元素（包括 7 个 2 和 2 个 0）。

非 1 元素的总数量为 9，所以输出 9。

测试用例2：

1、输入

3 3
0 0 0
0 2 0
0 0 0

2、输出

1

3、说明

初始矩阵大小为 3x3，(0,0) 元素被修改为 1，传播后矩阵为：

1 1 1
1 2 1
1 1 1

矩阵中只有一个非 1 元素（2），所以输出 1。

五、解题思路

1、为什么采用广度优先搜索BFS？

BFS 在逐层扩展问题中性能优异。在此问题中，感染逐步向周围扩散，与 BFS 的性质吻合。BFS 通过队列的先进先出特性，确保每一层的感染是按序处理的，避免漏掉任何可以传播的方向。

使用队列（FIFO）数据结构来存储每次感染扩散的节点。每次取出队列的节点，扩散到其周围的上下左右位置，将符合条件的新位置加入队列，表示它们将被下一轮感染。

2、具体步骤：

1. 初始化矩阵:
   • 首先，读取输入的矩阵大小 m 和 n，然后读取矩阵的元素内容。
   • 将矩阵的 [0,0] 元素设置为 1，表示起始感染的位置。
2. 传播感染：
   • 广度优先搜索（BFS）：使用队列来模拟感染的传播过程。首先，将初始感染位置 [0,0] 加入队列，然后每次从队列中取出一个位置，检 查其上下左右四个方向。如果该方向的元素为 0，将其修改为 1，表示感染扩散，并将该位置加入队列。
   • 采用 BFS 是因为感染是逐步向四周扩散的，这种逐层扩散的过程符合 BFS 的特性。
3. 边界检查：
   • 在扩散过程中，检查每个新位置是否在矩阵边界内，以避免越界错误。
   • 还要检查目标位置是否为 0，因为只有值为 0 的位置可以被感染。
4. 统计非 1 元素的个数：
   • 感染扩散完成后，遍历整个矩阵，统计值为 0 和 2 的元素数量，这两个元素代表未被感染的区域和免疫区域。
5. 输出结果：
   • 最后，输出矩阵中非 1 元素的数量。

3、时间复杂度

O(m * n)，其中 m 和 n 是矩阵的行数和列数。最坏情况下，所有的元素都需要被遍历和检查一次。

4、空间复杂度

O(m * n)，主要是队列中可能会存储矩阵中所有的元素位置，尤其是当所有元素都需要被感染或被检查时。

六、Python算法源码

使用 collections.deque 模拟队列进行 BFS 操作，读取输入矩阵大小和内容，并进行感染传播。

from collections import deque# 定义四个方向数组，分别代表上下左右的移动
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]def main():# 输入矩阵大小m, n = map(int, input().split())matrix = []# 输入矩阵内容for _ in range(m):matrix.append(list(map(int, input().split())))# 将 [0, 0] 位置修改为 1matrix[0][0] = 1# 使用队列进行广度优先搜索（BFS）以传播感染queue = deque()queue.append((0, 0))  # 初始位置加入队列while queue:x, y = queue.popleft()# 遍历四个方向for i in range(4):newX = x + dx[i]newY = y + dy[i]# 检查边界和感染条件if 0 <= newX < m and 0 <= newY < n and matrix[newX][newY] == 0:matrix[newX][newY] = 1  # 将值修改为 1，表示感染queue.append((newX, newY))  # 将新位置加入队列# 统计非1的元素个数（即0和2的个数）count = sum(matrix[i][j] in [0, 2] for i in range(m) for j in range(n))# 输出结果print(count)if __name__ == "__main__":main()

七、JavaScript算法源码

使用数组作为队列，shift 方法用于出队，模拟 BFS 感染过程，读取输入并输出结果。

function main() {// 定义四个方向数组，分别代表上下左右的移动const dx = [-1, 1, 0, 0];const dy = [0, 0, -1, 1];// 输入矩阵大小const input = prompt("Enter matrix size and elements:").split("\n");const [m, n] = input[0].split(' ').map(Number);let matrix = [];// 输入矩阵内容for (let i = 0; i < m; i++) {matrix.push(input[i + 1].split(' ').map(Number));}// 将 [0, 0] 位置修改为 1matrix[0][0] = 1;// 使用队列进行广度优先搜索（BFS）以传播感染let queue = [];queue.push([0, 0]); // 初始位置加入队列while (queue.length > 0) {let [x, y] = queue.shift();// 遍历四个方向for (let i = 0; i < 4; i++) {let newX = x + dx[i];let newY = y + dy[i];// 检查边界和感染条件if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] === 0) {matrix[newX][newY] = 1; // 将值修改为 1，表示感染queue.push([newX, newY]); // 将新位置加入队列}}}// 统计非1的元素个数（即0和2的个数）let count = 0;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (matrix[i][j] === 0 || matrix[i][j] === 2) {count++;}}}// 输出结果console.log(count);
}main();

八、C算法源码

使用数组模拟队列进行 BFS，由于 C 语言没有内置队列，手动实现一个队列结构，包含元素添加和移除的逻辑。

#include <stdio.h>#define MAX 100// 定义四个方向数组，分别代表上下左右的移动
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};typedef struct {int x, y;
} Point;int main() {int m, n;int matrix[MAX][MAX];Point queue[MAX * MAX];int front = 0, rear = 0;// 输入矩阵大小scanf("%d %d", &m, &n);// 输入矩阵内容for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {scanf("%d", &matrix[i][j]);}}// 将 [0, 0] 位置修改为 1matrix[0][0] = 1;// 使用队列进行广度优先搜索（BFS）以传播感染queue[rear++] = (Point){0, 0}; // 初始位置加入队列while (front < rear) {Point current = queue[front++];int x = current.x;int y = current.y;// 遍历四个方向for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查边界和感染条件if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {matrix[newX][newY] = 1; // 将值修改为 1，表示感染queue[rear++] = (Point){newX, newY}; // 将新位置加入队列}}}// 统计非1的元素个数（即0和2的个数）int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0 || matrix[i][j] == 2) {count++;}}}// 输出结果printf("%d\n", count);return 0;
}

九、C++算法源码

使用 STL 中的 queue 数据结构进行 BFS 操作，pair 用于存储坐标，并模拟感染传播。

#include <iostream>
#include <queue>using namespace std;// 定义四个方向数组，分别代表上下左右的移动
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};int main() {int m, n;cin >> m >> n;int matrix[m][n];// 输入矩阵内容for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> matrix[i][j];}}// 将 [0, 0] 位置修改为 1matrix[0][0] = 1;// 使用队列进行广度优先搜索（BFS）以传播感染queue<pair<int, int>> q;q.push({0, 0}); // 初始位置加入队列while (!q.empty()) {pair<int, int> current = q.front();q.pop();int x = current.first;int y = current.second;// 遍历四个方向for (int i = 0; i < 4; i++) {int newX = x + dx[i];int newY = y + dy[i];// 检查边界和感染条件if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {matrix[newX][newY] = 1; // 将值修改为 1，表示感染q.push({newX, newY}); // 将新位置加入队列}}}// 统计非1的元素个数（即0和2的个数）int count = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0 || matrix[i][j] == 2) {count++;}}}// 输出结果cout << count << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。