赞
踩
为了达到新冠疫情精准防控的需要,为了避免全员核酸检测带来的浪费,需要精准圈定可能被感染的人群。
现在根据传染病流调以及大数据分析,得到了每个人之间在时间、空间上是否存在轨迹的交叉。
现在给定一组确诊人员编号(X1, X2, X3, .... Xn),在所有人当中,找出哪些人需要进行核酸检测,输出需要进行核酸检测的人数。(注意:确诊病例自身不需要再做核酸检测)
需要进行核酸检测的人,是病毒传播链条上的所有人员,即有可能通过确诊病例所能传播到的所有人。
例如:A是确诊病例,A和B有接触、B和C有接触、C和D有接触、D和E有接触,那么B\C\D\E都是需要进行核酸检测的人。输入描述:
第一行为总人数N
第二行为确诊病例人员编号(确诊病例人员数量<N),用逗号分割
第三行开始,为一个N*N的矩阵,表示每个人员之间是否有接触,0表示没有接触,1表示有接触。
输出描述:
整数:需要做核酸检测的人数
备注:
人员编号从0开始
0<N<100
- import java.util.*;
-
- public class Main {
- public static void main(String[] args) {
- // int n = 5;
- // int[] target = new int[]{1, 2};
- // int[][] nums = new int[][]{{1, 1, 0, 1, 0}, {1, 1, 0, 0, 0}, {0, 0, 1, 0, 1}, {1, 0, 0, 1, 0}, {0, 0, 1, 0, 1}};
- // 处理数据
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
-
- String[] string1 = scanner.next().split(",");
- int[] target = new int[string1.length];
- for (int i = 0; i < target.length; i++) {
- target[i] = Integer.parseInt(string1[i]);
- }
- int[][] nums = new int[n][n];
- for (int i = 0; i < n; i++) {
- String[] string = scanner.next().split(",");
- for (int j = 0; j < n; j++) {
- nums[i][j] = Integer.parseInt(string[j]);
- }
- }
- // stack用于存储确诊人员和接触人员,依次从里面找
- Stack<Integer> stack = new Stack();
- // set进行去重,避免死循环
- HashSet<Integer> set = new HashSet<>();
- for (int i = 0; i < target.length; i++) {
- set.add(target[i]);
- stack.push(target[i]);
- }
- while (!stack.isEmpty()) {
- Integer pop = stack.pop();
- // 两个for循环判断是否存在秘接人员,注意set去重
- for (int i = 0; i < n; i++) {
- if (nums[i][pop] != 1 || set.contains(i)) {
- continue;
- }
- stack.add(i);
- set.add(i);
- }
- for (int i = 0; i < n; i++) {
- if (nums[pop][i] != 1 || set.contains(i)) {
- continue;
- }
- stack.add(i);
- set.add(i);
- }
- }
- System.out.println(set.size() - target.length);
- }
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。