马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
题目形貌
存在一个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)
二、实现步调详解
步调一：初始设置
- 将出发点(0,0)设为1（题目要求）
- 初始化队列，将出发点坐标加入队列
- 定义四个方向的位移数组（上下左右）
步调二：BFS扩散过程
- from collections import deque
- queue = 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+dy
- if 0<=nx<m and 0<=ny<n and grid[nx][ny]==0:
- grid[nx][ny] = 1
- queue.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
六、边界条件处理
- 全0矩阵：所有元素都会被感染，结果为0
- 出发点被2包围：仅出发点变为1，其他保持原样
- 极长传播路径：BFS仍能正确处理扩散顺序
- 超大矩阵：Python的deque能高效处理队列操作
通过BFS模仿感染过程，我们可以大概正确高效地盘算结果。关键点在于明白感染传播的特性，并选择合适的搜索算法进行模仿。该方法在时空复杂度上都能很好地应对题目要求的所有数据范围。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
