在一个 n \times nn×n的矩阵中,每个位置均有一个人 已知中间点(如 n = 5n=5,则中间点为 (3,3)(3,3))的那个人感染了病毒 对于每个感染病毒的人,他的上下左右四个人均会在下一分钟感染病毒 当然,已经感染病毒的人是
时间: 2024-04-02 14:32:14 浏览: 8
不会再次被感染的。请问,在 t 分钟后,有多少人感染了病毒?
这是一个传染病模型问题,可以使用 BFS(广度优先搜索)来解决。
具体步骤如下:
1. 将中间点加入队列,并标记为已访问。
2. 对于队列中的每一个点,遍历其上下左右四个位置,如果该位置没有被访问过并且有人,则将其加入队列,并标记为已访问。
3. 重复第二步,直到队列为空或者已经遍历了 t 次。
4. 统计被感染的人数。
代码示例(假设 n=5,中心点为(3,3),矩阵用 0 表示空位,1 表示有人):
```python
from collections import deque
# 初始化矩阵
n = 5
matrix = [[1] * n for _ in range(n)]
matrix[2][2] = 0
# 初始化队列和已访问列表
q = deque([(2, 2)])
visited = set([(2, 2)])
# BFS
t = 3
for i in range(t):
size = len(q)
for j in range(size):
x, y = q.popleft()
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited and matrix[nx][ny] == 1:
q.append((nx, ny))
visited.add((nx, ny))
# 统计感染人数
infected = 0
for i in range(n):
for j in range(n):
if matrix[i][j] == 1 and (i, j) in visited:
infected += 1
print(infected)
```
注意,这里假设已知中心点为 (3,3),因此直接将其加入队列。如果不知道中心点的位置,可以先遍历整个矩阵找到被感染的点,然后将其加入队列。