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. 首先，将输入的字符串转换为二维数组，表示地图。

2. 创建一个队列，将所有初始感染点（值为 1 的位置）加入队列。

3. 使用 BFS 进行扩散：

   • 每次从队列中取出一个感染点。
   • 检查这个点的上下左右四个相邻位置。
   • 如果相邻位置在地图范围内且未被感染，则将其感染并加入队列。

4. 记录扩散的天数，即 BFS 的层数。

5. 当队列为空时，检查是否所有区域都被感染。如果是，返回天数；否则，返回 -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