华为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);}}}

(完)