【华为机试】2023年真题B卷（python）-计算疫情扩散时间

一、题目

题目描述：

请根据给定的地图计算，多少天以后，全部区域都会被感染。
如果初始地图上所有区域全部都被感染，或者没有被感染区域，返回-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：
输入：
1,0,1,0,0,0,1,0,1?
输出：
2?
说明：
1天以后，地图中仅剩余中心点未被感染；2天以后，全部被感染。
示例2：
输入：
0,0,0,0
输出：
-1?
说明：
无感染区域
示例3：
输入：
1,1,1,1,1,1,1,1,1
输出：
-1
说明:
全部都感染 备注: 1<=N<200

四、要求

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++262144K，其他语言524288K

五、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-计算疫情扩散时间.py
@Time    :   2023/12/29 23:18:02
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

import math

# 定义四个方向的偏移量
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

def calculate_days_to_infect():
    # 读取输入并计算地图大小
    nums = [int(x) for x in input().split(",")]
    n = int(math.sqrt(len(nums)))

    # 创建二维矩阵并初始化为0
    matrix = [[0 for _ in range(n)] for _ in range(n)]

    infected_zones = []
    for i in range(n):
        for j in range(n):
            matrix[i][j] = nums[i * n + j]
            if matrix[i][j] == 1:
                infected_zones.append([i, j])

    if len(infected_zones) == 0 or len(infected_zones) == len(nums):
        return -1
    else:
        healthy = len(nums) - len(infected_zones)

        result = 0
        while len(infected_zones) > 0 and healthy > 0:
            new_infected_zones = []

            for x, y in infected_zones:
                result = matrix[x][y] + 1

                for direction in directions:
                    next_x = x + direction[0]
                    next_y = y + direction[1]

                    if next_x < 0 or next_x >= n or next_y < 0 or next_y >= n:
                        continue

                    if matrix[next_x][next_y] == 0:
                        healthy -= 1
                        matrix[next_x][next_y] = result
                        new_infected_zones.append([next_x, next_y])

            infected_zones = new_infected_zones

        return result - 1

# 调用方法并打印结果
result = calculate_days_to_infect()
print(result)