软件公司招聘网站,做网站建设的联系电话,专注于上海seo做网站建设,编程如何自学题目部分
题目计算疫情扩散时间难度难题目说明在一个地图中(地图由 n * n 个区域组成)有部分区域被感染病菌感染区域每天都会把周围(上下左右)的4个区域感染。 请根据给定的地图计算多少天以后#xff0c;全部区域都会被感染。 如果初始地图上所有区域全部都被感染#xff0…题目部分
题目计算疫情扩散时间难度难题目说明在一个地图中(地图由 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;SetInteger diseaseSet new HashSetInteger();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, SetInteger 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));SetInteger newDiseaseSet new HashSetInteger();newDiseaseSet.addAll(diseaseSet);while (diseaseSet.size() ! arrCount) {for (IteratorInteger 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, SetInteger 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);}}} (完)
