【华为OD机试真题】【2024年E卷】数值同化-队列BFS(C++/Java/Python)

分值：200

题目描述

存在一个 m * n 的 二维数组只，其成员取值范围为0, 1, 2。其中值为1的元素具备同化特性，每经过1S，将上下左右值为0的元素同化为1。而值为2的元素，免疫同化。
将数组所有成员随机初始化只为0或2，再将矩阵的[0,0]元素修改成1，在经过足够长的时间后，求矩阵中有多少个元素是0或2(即0和2数量之和)。
输入描述:
输入的前两个数字是矩阵大小n 和m。
接着输入n行m列，表示矩阵信息。
输出描述:
返回矩阵中非 1的元素个数。

示例1
输入：
4 4
0 0 0 0
0 2 0 0
0 0 2 0
0 0 0 2
输出：
3
解释：
除了矩阵中 3 个值为2的元素，其他元素全部同化为1了。

示例2
输入：
4 4
0 2 0 0
0 2 0 0
0 2 0 0
0 2 0 0
输出：
12
解释：
只有第一列被同化为1了，第2、3、4列没有被同化，因为第二列全是值为2的元素，阻挡住同化了。

Tips:

• 0 < m, n <= 30

思路

• 从将上下左右值为0的元素同化为1 这点可以联系到BFS，这是一道很经典的宽度优先搜索的题目，可以当做模板题进行练习。
• 从[0, 0]开始出发，只有值为0的元素才能被同化，所以只将1周围的 0 元素放进队列，直到队列为空即可。
• 答案要求返回矩阵中非 1的元素个数。可以在遍历的同时进行计算，每当有一个元素被同化，那么ans就减一。

复杂度分析

• 时间复杂度： $O(n\ast m)$，其中N和M分别为矩阵的行长跟列长，每个位置只需要访问一次。
• 空间复杂度： $O(n\ast m)$，其中N和M分别为矩阵的行长跟列长，用于存储矩阵信息。

AC 代码

C++ 版

#include <bits/stdc++.h>
using namespace std;
int main()
{int n, m, ans, dis[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};cin >> n >> m;vector<vector<int>> mx(n, vector<int>(m));for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> mx[i][j];}}mx[0][0] = 1;// 一开始 0 跟 2 的个数之和, 后面每次有同化的就 -1 即可ans = n * m - 1;queue<pair<int, int>> q;q.push({0, 0});while (!q.empty()){auto t = q.front();q.pop();for (int i = 0; i < 4; i++){int x = t.first + dis[i][0], y = t.second + dis[i][1];if (x >= 0 && x < n && y >= 0 && y < m && mx[x][y] == 0){mx[x][y] = 1;ans--;q.push({x, y});}}}cout << ans << endl;return 0;
}

JAVA 版

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int ans;int[][] dis = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int[][] mx = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {mx[i][j] = scanner.nextInt();}}mx[0][0] = 1;ans = n * m - 1;Queue<int[]> q = new LinkedList<>();q.add(new int[]{0, 0});while (!q.isEmpty()) {int[] t = q.poll();for (int i = 0; i < 4; i++) {int x = t[0] + dis[i][0];int y = t[1] + dis[i][1];if (x >= 0 && x < n && y >= 0 && y < m && mx[x][y] == 0) {mx[x][y] = 1;ans--;q.add(new int[]{x, y});}}}System.out.println(ans);}
}

Python 版

from collections import dequen, m = map(int, input().split())
ans = 0
dis = [[-1, 0], [1, 0], [0, -1], [0, 1]]mx = []
for _ in range(n):mx.append(list(map(int, input().split())))mx[0][0] = 1
ans = n * m - 1
q = deque([(0, 0)])while q:t = q.popleft()for i in range(4):x = t[0] + dis[i][0]y = t[1] + dis[i][1]if 0 <= x < n and 0 <= y < m and mx[x][y] == 0:mx[x][y] = 1ans -= 1q.append((x, y))print(ans)