华为OD机试_2025 B卷_返回矩阵中非1的元素个数（Python，100分）（附详细解题思路）

题目描述

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

其中值为1的元素具备同化特性，每经过1S，将上下左右值为0的元素同化为1。

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

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

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

输出描述
返回矩阵中非1的元素个数。

用例

输入	4 4 0 0 0 0 0 2 2 2 0 2 0 0 0 2 0 0
输出	9
说明	输入数字前两个数字是矩阵大小。后面的数字是矩阵内容。 起始位置(0,0)被修改为1后，最终只能同化矩阵为： 1 1 1 1 1 2 2 2 1 2 0 0 1 2 0 0 所以矩阵中非1的元素个数为9

解题思路：广度优先搜索（BFS）模拟感染过程

这道题的核心是模拟具有传染特性的1元素在矩阵中的扩散过程。我们需要找出所有能够被感染的0元素，并最终统计无法被感染的0和免疫的2的数量总和。

---

一、核心思路图解

1. 问题本质

矩阵中存在三种数值：

• 0：可以被同化的普通元素
• 1：具有同化能力的源头
• 2：无法被同化的元素

要求计算在无限时间后，未被感染的0和所有2的总数。

2. 关键观察

• 感染的传播规律：1元素每秒钟向上下左右四个方向扩散，但只能感染相邻的0元素
• 传播阻断条件：遇到2时会完全阻断传播路径
• 最终状态等价性：无限时间后的状态等价于通过BFS遍历所有可达的0元素

3. 算法选择

使用广度优先搜索（BFS） 的原因：

• 天然符合感染扩散的层次性（每层对应1秒的扩散范围）
• 能够高效标记所有可达的0元素
• 时间复杂度O(mn)，空间复杂度O(mn)

---

二、实现步骤详解

步骤一：初始设置

1. 将起点(0,0)设为1（题目要求）
2. 初始化队列，将起点坐标加入队列
3. 定义四个方向的位移数组（上下左右）

步骤二：BFS扩散过程

from collections import dequequeue = deque()
queue.append((0, 0))  # 初始感染源directions = [(-1,0),(1,0),(0,-1),(0,1)]  # 移动方向while queue:x, y = queue.popleft()for dx, dy in directions:nx, ny = x+dx, y+dy# 检查边界和是否可感染if 0<=nx<rows and 0<=ny<cols and grid[nx][ny]==0:grid[nx][ny] = 1       # 标记为已感染queue.append((nx, ny)) # 加入新感染源

步骤三：统计结果

遍历整个矩阵，计数所有非1元素：

count = 0
for row in grid:for num in row:if num != 1:count += 1
print(count)

---

三、代码实现与解析

from collections import deque# 读取输入
m, n = map(int, input().split())
grid = []
for _ in range(m):grid.append(list(map(int, input().split())))# 设置初始感染源
grid[0][0] = 1# BFS初始化
queue = deque([(0, 0)])
directions = [(-1,0),(1,0),(0,-1),(0,1)]# 扩散过程
while queue:x, y = queue.popleft()for dx, dy in directions:nx, ny = x+dx, y+dyif 0<=nx<m and 0<=ny<n and grid[nx][ny]==0:grid[nx][ny] = 1queue.append((nx, ny))# 统计未被感染的元素
result = 0
for row in grid:result += sum(1 for num in row if num != 1)
print(result)

---

四、复杂度与优化分析

时间复杂度

• BFS过程：O(mn)，每个节点最多入队一次
• 最终统计：O(mn)
• 总复杂度：O(mn)，在1000x1000的矩阵中也能高效运行

空间复杂度

• 队列最大长度：O(mn)（极端情况全为0）
• 矩阵存储：O(mn)
• 总空间：O(mn)

---

五、典型案例验证

以题目示例说明：

输入矩阵：
0 0 0 0
0 2 2 2 
0 2 0 0 
0 2 0 0 处理后矩阵：
1 1 1 1
1 2 2 2 
1 2 0 0 
1 2 0 0 未被感染元素分布：
第二行：3个2
第三行：2个0 + 1个2
第四行：2个0 + 1个2
总和：3+3+3=9

---

六、边界条件处理

1. 全0矩阵：所有元素都会被感染，结果为0
2. 起点被2包围：仅起点变为1，其他保持原样
3. 极长传播路径：BFS仍能正确处理扩散顺序
4. 超大矩阵：Python的deque能高效处理队列操作

---

通过BFS模拟感染过程，我们能够准确高效地计算结果。关键点在于理解感染传播的特性，并选择合适的搜索算法进行模拟。该方法在时空复杂度上都能很好地应对题目要求的所有数据范围。