华为OD机考算法题：计算疫情扩散时间
题目部分
| 题目 | 计算疫情扩散时间 |
| 难度 | 难 |
| 题目说明 | 在一个地图中(地图由 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 | |
| 输入 | 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 |
| 说明 | 已经全部被感染 |
解读与分析
题目解读：
给定一个一维数组，数组中的数字为 0、1，把它转换成对应的二维数组。如果数组的初始值全为 0 或全为 1，返回 -1。每一天，数字为 1 的会把其上下左右 4 个方向的值改成 1。求多少天后，全部都变成 1。
分析与思路：
实现机制比较简单，先解析输入数据，接着统计 0 和 1 的数字，之后把 1 上下左右的数字变成 1，再统计，直到所有的数据都变成 1。具体实现步骤如下：
1. 解析数据。把输入数据解析成一维数组，记录所有包含 1 的数组下标。
2. 统计。如果 1 的个数等于所有数字个数，或 1 的个数为 0，返回 -1。否则，进行第 3 步。
3. 初始换当前感染数据。把所有值为 1 的数字下标放到集合中，设为 value1Set。
4. 更新感染数字。遍历 value1Set，计算当天之后所有值为 1 的下标，放到集合 newValue1Set中。当前天数加1。
5. 统计 newValue1Set 的元素个数，如果等于全部个数，则全部感染，返回当前天数。否则，把 newValue1Set 赋值给 value1Set，继续执行步骤 4。
此方法的时间复杂度为 O( n平方 )，空间复杂度为 O(n)。
代码实现
Java代码
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;/*** 计算疫情扩散时间* * @since 2023.11.01* @version 0.1* @author Frank**/
public class DiseaseSpread {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] inputArr = input.split(",");int arrCount = inputArr.length;Set<Integer> diseaseSet = new HashSet<Integer>();for (int i = 0; i < arrCount; i++) {int value = Integer.parseInt(inputArr[i]);if (value == 1) {diseaseSet.add(i);}}processDiseaseSpread(arrCount, diseaseSet);}}private static void processDiseaseSpread(int arrCount, Set<Integer> diseaseSet) {if (diseaseSet.size() == 0 || diseaseSet.size() == arrCount) {System.out.println(-1);return;}int days = 0;// 避免误差，使用 Math.round。int dimension = (int) Math.round(Math.sqrt(arrCount));Set<Integer> newDiseaseSet = new HashSet<Integer>();newDiseaseSet.addAll(diseaseSet);while (diseaseSet.size() != arrCount) {for (Iterator<Integer> iter = diseaseSet.iterator(); iter.hasNext();) {int coords = iter.next();updateNewCoords(dimension, coords, newDiseaseSet);}days++;if (newDiseaseSet.size() == arrCount) {System.out.println(days);return;}diseaseSet = newDiseaseSet;}}private static void updateNewCoords(int dimension, int coords, Set<Integer> newDiseaseSet) {int i = coords / dimension;int j = coords % dimension;int[][] fourDirections = { { i, j - 1 }, { i, j + 1 }, { i - 1, j }, { i + 1, j } };for (int k = 0; k < fourDirections.length; k++) {int curI = fourDirections[k][0];int curJ = fourDirections[k][1];if (curI < 0 || curJ < 0 || curI >= dimension || curJ >= dimension) {continue;}Integer curCoords = curI * dimension + curJ;if (!newDiseaseSet.contains(curCoords)) {newDiseaseSet.add(curCoords);}}}}
JavaScript代码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var inputArr = line.split(",");var arrCount = inputArr.length;var diseaseSet = new Set();for (var i = 0; i < arrCount; i++) {var value = parseInt(inputArr[i]);if (value == 1) {diseaseSet.add(i);}}processDiseaseSpread(arrCount, diseaseSet);}
}();function processDiseaseSpread(arrCount, diseaseSet) {if (diseaseSet.size == 0 || diseaseSet.size == arrCount) {console.log(-1);return;}var days = 0;// 避免误差，使用 Math.round。var dimension = Math.round(Math.sqrt(arrCount));while (diseaseSet.size != arrCount) {var newDiseaseSet = new Set();for (var i of diseaseSet) {newDiseaseSet.add(i);updateNewCoords(dimension, i, newDiseaseSet);}days++;if (newDiseaseSet.size == arrCount) {console.log(days);return;}diseaseSet = newDiseaseSet;}
}function updateNewCoords(dimension, coords, newDiseaseSet) {var i = parseInt(coords / dimension);var j = coords % dimension;var fourDirections = [[i, j - 1],[i, j + 1],[i - 1, j],[i + 1, j]];for (var k = 0; k < fourDirections.length; k++) {var curI = fourDirections[k][0];var curJ = fourDirections[k][1];if (curI < 0 || curJ < 0 || curI >= dimension || curJ >= dimension) {continue;}var curCoords = curI * dimension + curJ;if (!newDiseaseSet.has(curCoords)) {newDiseaseSet.add(curCoords);}}}(完)