E卷-计算疫情扩散时间(200分)
计算疫情扩散时间
问题描述
在一个 的地图中，有部分区域被感染病菌。感染区域每天都会把周围（上下左右）的 4 个区域感染。请根据给定的地图计算，多少天以后，全部区域都会被感染。如果初始地图上所有区域全部都被感染，或者没有被感染区域，返回 -1。
输入格式
一行 个数字（只包含 0、1，不会有其他数字）表示一个地图，数字间用逗号分割，0 表示未感染区域，1 表示已经感染区域。每
个数字表示地图中一行，输入数据共表示
行
列的区域地图。
输出格式
一个整数，表示经过多少天以后，全部区域都被感染。
样例输入 1
1,0,1,0,0,0,1,0,1
样例输出 1
2
样例解释 1
1 天以后，地图中仅剩余中心点未被感染；2 天以后，全部被感染。
样例输入 2
0,0,0,0
样例输出 2
-1
样例解释 2
无感染区域。
样例输入 3
1,1,1,1,1,1,1,1,1
样例输出 3
-1
样例解释 3
全部都感染。
数据范围
题解
这道题目本质上是一个多源广度优先搜索（BFS）问题。
需要模拟病菌从多个初始感染点同时向外扩散的过程。
解题思路如下：
-
首先，将输入的字符串转换为二维数组，表示地图。
-
创建一个队列，将所有初始感染点（值为 1 的位置）加入队列。
-
使用 BFS 进行扩散：
- 每次从队列中取出一个感染点。
- 检查这个点的上下左右四个相邻位置。
- 如果相邻位置在地图范围内且未被感染，则将其感染并加入队列。
-
记录扩散的天数，即 BFS 的层数。
-
当队列为空时，检查是否所有区域都被感染。如果是，返回天数；否则，返回 -1。
参考代码
- Python
from collections import deque
def calculate_infection_time(map_str):
# 将输入字符串转换为二维数组
rows = map_str.split(',')
n = int(len(rows) ** 0.5)
grid = [list(map(int, rows[i:i+n])) for i in range(0, len(rows), n)]
# 如果全部感染或全部未感染，返回-1
if all(all(cell == 1 for cell in row) for row in grid) or all(all(cell == 0 for cell in row) for row in grid):
return -1
# 定义四个方向：上、下、左、右
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 初始化队列和已访问集合
queue = deque()
visited = set()
# 将所有初始感染点加入队列
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
queue.append((i, j, 0)) # (行, 列, 天数)
visited.add((i, j))
max_days = 0
# BFS
while queue:
x, y, days = queue.popleft()
max_days = max(max_days, days)
# 检查四个方向
for dx, dy in directions:
nx, ny = x + dx, y + dy
# 如果新位置在网格内且未被访问过
if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited:
visited.add((nx, ny))
queue.append((nx, ny, days + 1))
# 检查是否所有位置都被感染
return max_days if len(visited) == n * n else -1
# 读取输入并处理
input_str = input().strip()
print(calculate_infection_time(input_str))
- C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX_N 200 // 定义最大网格大小
#define MAX_QUEUE 40000 // 定义最大队列大小
// 定义点结构，包含坐标和天数
typedef struct {
int x, y, days;
} Point;
// 全局队列
Point queue[MAX_QUEUE];
int front = 0, rear = 0;
// 入队函数
void enqueue(int x, int y, int days) {
queue[rear].x = x;
queue[rear].y = y;
queue[rear].days = days;
rear++;
}
// 出队函数
Point dequeue() {
return queue[front++];
}
// 返回两个整数中的较大值
int max(int a, int b) {
return a > b ? a : b;
}
// 计算感染时间的主函数
int calculateInfectionTime(const char* mapStr) {
int rows[MAX_N * MAX_N];
int rowCount = 0;
// 解析输入字符串
char* token = strtok((char*)mapStr, ",");
while (token != NULL) {
rows[rowCount++] = atoi(token);
token = strtok(NULL, ",");
}
// 计算网格大小并创建网格
int n = (int)sqrt(rowCount);
int grid[MAX_N][MAX_N];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = rows[i * n + j];
}
}
// 检查是否全部感染或全部健康
int allInfected = 1, allHealthy = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) allInfected = 0;
if (grid[i][j] == 1) allHealthy = 0;
}
}
if (allInfected || allHealthy) return -1;
// 定义四个方向：上、下、左、右
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 初始化访问数组和队列
int visited[MAX_N][MAX_N] = {0};
front = rear = 0;
// 将所有初始感染点加入队列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
enqueue(i, j, 0);
visited[i][j] = 1;
}
}
}
int maxDays = 0;
// BFS 主循环
while (front < rear) {
Point p = dequeue();
maxDays = max(maxDays, p.days);
// 检查四个方向
for (int d = 0; d < 4; d++) {
int nx = p.x + directions[d][0];
int ny = p.y + directions[d][1];
// 如果新位置在网格内且未被访问过
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
visited[nx][ny] = 1;
enqueue(nx, ny, p.days + 1);
}
}
}
// 计算总共访问的位置数
int totalVisited = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j]) totalVisited++;
}
}
// 如果所有位置都被访问，返回最大天数；否则返回-1
return totalVisited == n * n ? maxDays : -1;
}
int main() {
char input[MAX_N * MAX_N * 2];
fgets(input, sizeof(input), stdin);
input[strcspn(input, "\n")] = 0; // 移除换行符
printf("%d\n", calculateInfectionTime(input));
return 0;
}
- Javascript
function calculateInfectionTime(mapStr) {
// 将输入字符串转换为二维数组
const rows = mapStr.split(',');
const n = Math.sqrt(rows.length);
const grid = [];
for (let i = 0; i < n; i++) {
grid.push(rows.slice(i * n, (i + 1) * n).map(Number));
}
// 如果全部感染或全部未感染，返回-1
if (grid.every(row => row.every(cell => cell === 1)) || grid.every(row => row.every(cell => cell === 0))) {
return -1;
}
// 定义四个方向：上、下、左、右
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
// 初始化队列和已访问集合
const queue = [];
const visited = new Set();
// 将所有初始感染点加入队列
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
queue.push([i, j, 0]); // [行, 列, 天数]
visited.add(`${i},${j}`);
}
}
}
let maxDays = 0;
// BFS
while (queue.length > 0) {
const [x, y, days] = queue.shift();
maxDays = Math.max(maxDays, days);
// 检查四个方向
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
// 如果新位置在网格内且未被访问过
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited.has(`${nx},${ny}`)) {
visited.add(`${nx},${ny}`);
queue.push([nx, ny, days + 1]);
}
}
}
// 检查是否所有位置都被感染
return visited.size === n * n ? maxDays : -1;
}
// 读取输入并处理
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.question('', (input) => {
console.log(calculateInfectionTime(input.trim()));
rl.close();
});
- Java
import java.util.*;
public class Main {
static class Point {
int x, y, days;
Point(int x, int y, int days) {
this.x = x;
this.y = y;
this.days = days;
}
}
public static int calculateInfectionTime(String mapStr) {
// 将输入字符串转换为二维数组
String[] rows = mapStr.split(",");
int n = (int) Math.sqrt(rows.length);
int[][] grid = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = Integer.parseInt(rows[i * n + j]);
}
}
// 如果全部感染或全部未感染，返回-1
boolean allInfected = true, allHealthy = true;
for (int[] row : grid) {
for (int cell : row) {
if (cell == 0) allInfected = false;
if (cell == 1) allHealthy = false;
}
}
if (allInfected || allHealthy) return -1;
// 定义四个方向：上、下、左、右
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 初始化队列和已访问集合
Queue<Point> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
// 将所有初始感染点加入队列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
queue.offer(new Point(i, j, 0));
visited.add(i + "," + j);
}
}
}
int maxDays = 0;
// BFS
while (!queue.isEmpty()) {
Point p = queue.poll();
maxDays = Math.max(maxDays, p.days);
// 检查四个方向
for (int[] dir : directions) {
int nx = p.x + dir[0];
int ny = p.y + dir[1];
// 如果新位置在网格内且未被访问过
if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited.contains(nx + "," + ny)) {
visited.add(nx + "," + ny);
queue.offer(new Point(nx, ny, p.days + 1));
}
}
}
// 检查是否所有位置都被感染
return visited.size() == n * n ? maxDays : -1;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine().trim();
System.out.println(calculateInfectionTime(input));
scanner.close();
}
}
- Cpp
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;
struct Point {
int x, y, days;
Point(int x, int y, int days) : x(x), y(y), days(days) {}
};
int calculateInfectionTime(const string& mapStr) {
// 将输入字符串转换为二维数组
vector<int> rows;
stringstream ss(mapStr);
string item;
while (getline(ss, item, ',')) {
rows.push_back(stoi(item));
}
int n = sqrt(rows.size());
vector<vector<int>> grid(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
grid[i][j] = rows[i * n + j];
}
}
// 如果全部感染或全部未感染，返回-1
bool allInfected = true, allHealthy = true;
for (const auto& row : grid) {
for (int cell : row) {
if (cell == 0) allInfected = false;
if (cell == 1) allHealthy = false;
}
}
if (allInfected || allHealthy) return -1;
// 定义四个方向：上、下、左、右
vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 初始化队列和已访问集合
queue<Point> q;
unordered_set<string> visited;
// 将所有初始感染点加入队列
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
q.push(Point(i, j, 0));
visited.insert(to_string(i) + "," + to_string(j));
}
}
}
int maxDays = 0;
// BFS
while (!q.empty()) {
Point p = q.front();
q.pop();
maxDays = max(maxDays, p.days);
// 检查四个方向
for (const auto& dir : directions) {
int nx = p.x + dir.first;
int ny = p.y + dir.second;
// 如果新位置在网格内且未被访问过
string key = to_string(nx) + "," + to_string(ny);
if (nx >= 0 && nx < n && ny >= 0 && ny < n && visited.find(key) == visited.end()) {
visited.insert(key);
q.push(Point(nx, ny, p.days + 1));
}
}
}
// 检查是否所有位置都被感染
return visited.size() == n * n ? maxDays : -1;
}
int main() {
string input;
getline(cin, input);
cout << calculateInfectionTime(input) << endl;
return 0;
}
OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记
