题目部分
题目 | 计算疫情扩散时间 |
难度 | 难 |
题目说明 | 在一个地图中(地图由 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代码
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);
}
}
}
(完)