【华为OD-E卷 - 计算疫情扩散时间 100分（python、java、c++、js、c）】
题目
在一个地图中(地图由n*n个区域组成），有部分区域被感染病菌。 感染区域每天都会把周围（上下左右）的4个区域感染。 请根据给定的地图计算，多少天以后，全部区域都会被感染。 如果初始地图上所有区域全部都被感染，或者没有被感染区域，返回-1
输入描述
- 一行N*N个数字（只包含0,1，不会有其他数字）表示一个地图，数字间用,分割，0表示未感染区域，1表示已经感染区域 每N个数字表示地图中一行，输入数据共表示N行N列的区域地图。
例如输入1,0,1,0,0,0,1,0,1，表示地图
1,0,1 0,0,0 1,0,1
输出描述
- 一个整数，表示经过多少天以后，全部区域都被感染 1<=N<200
备注
用例
用例一：
输入：
1,0,1,0,0,0,1,0,1
- 1
输出：
2
- 1
用例二：
输入：
0,0,0,0
- 1
输出：
-1
- 1
用例三：
输入：
1,1,1,1,1,1,1,1,1
- 1
输出：
-1
- 1
python解法
- 解题思路：
- 这段代码模拟了一个病毒在二维网格中传播的过程，类似于传染病的传播模型。目标是计算完全感染整个网格所需的天数，或者判断是否无法完全感染。以下是具体步骤：
输入与网格构造：
输入一维数组 arr，表示一个大小为
?
×
?
n×n 的网格。
将一维数组转化为二维网格 grid，其中：
值为 1 表示感染源。
值为 0 表示未感染区域。
初始化状态：
用一个队列 queue 存储所有初始感染源的位置。
统计未感染区域的数量 uninfected。
BFS 传播：
使用广度优先搜索 (BFS) 模拟感染传播。
每次从队列中取出当前感染源，尝试感染其相邻的未感染区域。
每传播一次（即一轮 BFS 扩展）计为一天，直至：
所有区域被感染，返回所需天数。
无法继续传播且仍有未感染区域，返回 -1。
特殊情况处理：
如果初始状态下没有感染源或没有未感染区域，直接返回 -1
from collections import deque
def bfs_infection(arr):
# 获取网格的边长 n，并将一维数组转为二维网格
n = int(len(arr) ** 0.5) # 网格为 n x n
grid = [arr[i * n:(i + 1) * n] for i in range(n)] # 转换为二维列表
queue = deque() # 用于存储当前的感染源位置
uninfected = 0 # 统计未感染区域的数量
# 遍历网格，初始化队列和未感染区域计数
for i in range(n):
for j in range(n):
if grid[i][j] == 1: # 如果是感染源
queue.append((i, j)) # 加入队列
else:
uninfected += 1 # 统计未感染区域
# 特殊情况：如果初始时没有未感染区域或感染源，返回 -1
if uninfected == 0:
return -1
if len(queue) == 0:
return -1
days = 0 # 记录传播天数
# 定义四个方向（上、下、左、右）
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 开始 BFS 传播
while queue and uninfected > 0:
# 遍历当前队列中的所有感染源位置
for _ in range(len(queue)):
x, y = queue.popleft() # 获取当前感染源位置
# 遍历四个方向
for dx, dy in directions:
nx, ny = x + dx, y + dy # 计算相邻位置
# 如果相邻位置有效且未感染
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
grid[nx][ny] = 1 # 感染该位置
queue.append((nx, ny)) # 将新感染位置加入队列
uninfected -= 1 # 未感染区域计数减少
days += 1 # 一轮传播结束，天数增加
# 如果所有区域被感染，返回所需天数；否则返回 -1
return days if uninfected == 0 else -1
# 从输入读取一维数组，元素以逗号分隔
input_arr = list(map(int, input().split(",")))
# 输出完全感染所需天数
print(bfs_infection(input_arr))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
java解法
- 解题思路
- 这段代码使用 BFS（广度优先搜索）算法来模拟病毒在二维网格中的传播过程，目标是计算感染整个网格所需的最小天数，或者判断是否无法完全感染。以下是具体步骤：
输入与网格构造：
输入是以逗号分隔的一维数组表示
?
×
?
n×n 的网格。
将一维数组转化为二维布尔数组 infected，其中：
true 表示该位置已感染。
false 表示该位置未感染。
初始化状态：
用队列 queue 存储所有初始感染源的位置。
统计未感染的健康区域数量 healthyCount。
特殊情况处理：
如果初始状态下没有感染源（队列为空）或所有区域已被感染，直接返回 -1。
BFS 传播：
每轮 BFS 处理所有当前感染源位置，尝试向四个方向传播。
每传播一次（即一轮 BFS 扩展）计为一天。
当所有健康区域被感染时停止传播，输出所需天数。
结果返回：
如果所有区域都被感染，返回天数。
如果无法完全感染，返回 -1。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入并解析为字符串数组
String[] input = sc.nextLine().split(",");
// 计算网格的边长 n
int n = (int) Math.sqrt(input.length);
// 创建布尔数组表示感染状态
boolean[][] infected = new boolean[n][n];
// 使用队列存储感染源位置
Queue<int[]> queue = new LinkedList<>();
// 统计健康区域的数量
int healthyCount = 0;
// 初始化网格状态、队列和健康区域计数
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 如果当前位置是感染源
infected[i][j] = input[i * n + j].equals("1");
if (infected[i][j]) {
queue.offer(new int[]{i, j}); // 将感染源加入队列
} else {
healthyCount++; // 统计健康区域
}
}
}
// 如果没有感染源或没有健康区域，直接返回 -1
if (queue.isEmpty() || healthyCount == 0) {
System.out.println(-1);
return;
}
int days = 0; // 记录传播天数
// 定义四个方向（上、下、左、右）
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 开始 BFS 传播
while (!queue.isEmpty() && healthyCount > 0) {
int size = queue.size(); // 当前轮次感染源的数量
days++; // 每轮传播计为一天
for (int i = 0; i < size; i++) {
int[] cell = queue.poll(); // 取出当前感染源位置
// 遍历四个方向
for (int[] dir : directions) {
int newX = cell[0] + dir[0];
int newY = cell[1] + dir[1];
// 判断相邻位置是否有效且未感染
if (newX >= 0 && newX < n && newY >= 0 && newY < n && !infected[newX][newY]) {
infected[newX][newY] = true; // 感染该位置
healthyCount--; // 健康区域数量减少
queue.offer(new int[]{newX, newY}); // 将新感染位置加入队列
}
}
}
}
// 如果所有区域被感染，输出天数；否则输出 -1
System.out.println(days);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
C++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
更新中
- 1
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：