[华为OD]C卷精准核算检测 100

本文主要是介绍[华为OD]C卷精准核算检测 100，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

为了达到新冠疫情精准防控的需要，为了避免全员核酸检测Q带来的浪费，需要精准圈定可

能被感染的人群。现在根据传染病流调以及大数据分析，得到了每个人之间在时间、空间上是

否存在轨迹的交叉现在给定一组确诊人员编号（ X1,X2,X3...Xn）在所有人当中，找出哪些人需要

进行核酸检测，输出需要进行核酸检测的人数。

注意:确诊病例自身不需要再做核酸检测）需要进行核酸检测的人，是病毒传播链条上的所有人

员，即有可能通过确诊病例所能传播到的所有人。

例如:A是确诊病例,A和B有接触、B和C有接触C和D有接触，D和E有接触。那么B、C、D、E

都是需要进行核酸检测的

输入描述

第一行为总人数N

第二行为确证病例人员编号（确证病例人员数量<N） ,用逗号隔开接下来N行，每一行有N个数

字，用逗号隔开，其中第i行的第个j数字表名编号i是否与编号j接触过。0表示没有接触，1表示

有接触

备注

人员编号从0开始

0< N <100

输出描述

输出需要做核酸检测的人数

示例1:

输入：

1,2

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

输出

说明：

编号为1、2号的人员为确诊病例1号与0号有接触，0号与3号有接触，2号54号有接触。所以,

需要做核酸检测的人是0号、3号、4号，总计3人要进行核酸检测。

题解：

方法1：可以采用递归，这个比较好理解。建立一个Map<Integer, List<Integer>> patientsContact，存储的是对应的人员编号和他接触人的编号。另外一个是建立一个Set<Integer> result,存储的是需要进行核算检测的人员编号。另一个就是建立初始化为0的数组visited[]，数组大小和总人数一致，里面visited[i]，就表示编号为第i+1的人员对应的接触人员是否已经检查过了，检查过了那么visited[i]=1. 而递归的终点就是result里面的所有数，都检查过了。

方法2，采用dfs来解析，这个相对有点没相处来，代码也放在下面

代码：

import java.util.*;public class FindDis {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int patients = Integer.valueOf(sc.nextLine());String needFind[] = sc.nextLine().split(",");int visited[] = new int[patients];for (int i = 0; i < patients; i++) {visited[i] = 0;}Map<Integer, List<Integer>> patientsContact = new HashMap<>();Set<Integer> result = new HashSet<>();for (int i = 0; i < patients; i++) {String contatcs[] = sc.nextLine().split(",");List<Integer> contactsList = new ArrayList<>();for (int j = 0; j < contatcs.length; j++) {if (j != i && contatcs[j].equals("1")) {if (contactsList.contains(j)) {continue;} else {contactsList.add(j);}}}patientsContact.put(i, contactsList);}//初始检测for (int i = 0; i < needFind.length; i++) {int present = Integer.valueOf(needFind[i]) - 1;  //人员的编号对应数组位置是大1的，所以这边直接减1 就能更数组对应起来了visited[present] = 1;result.add(present);List<Integer> needs = patientsContact.get(present);result.addAll(needs);}contact(visited, result, patientsContact);System.out.println(result.size());}// 轮询检测private static void contact(int[] visited, Set<Integer> result, Map<Integer, List<Integer>> patientsContact) {List<Integer> resultList = new ArrayList<>();resultList.addAll(result);Collections.sort(resultList);for (int i : resultList) {if (visited[i] == 1) {continue;} else {visited[i] = 1;List<Integer> needs = patientsContact.get(i);result.addAll(needs);contact(visited, result, patientsContact);}}}
}

dfs code

import java.util.Scanner;
import java.util.*;
import java.util.stream.Stream;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;public class Main { public static int[] target;public static int[][] matrix;public static int[] visited;public static int n;public static void main(String[] args) {Scanner in = new Scanner(System.in);n = Integer.parseInt(in.nextLine());target = split(in.nextLine());visited = new int[n];matrix = new int[n][n];for(int i=0;i<n;i++){int[] tmp = split(in.nextLine());visited[i] = 0;for(int j=0;j<n;j++){matrix[i][j] = tmp[j];}}for(int i=0;i<target.length;i++){dfs(target[i]);}int result = 0;int i=0;while(true){if(i>=n){break;} else {if (visited[i]==1) {boolean flag = false;for(int j=0;j<target.length;j++){if(target[j] == i){flag = true;break;}}if(!flag) {result += 1;}}}i+=1;}System.out.println(result);}public static void dfs(int index) {visited[index] = 1;int i=0;while(true){if(i>=n){break;} else {if (matrix[index][i] == 1 && visited[i]==0) {dfs(i); }}i+=1;}}public static int[] split(String input_str){String[] tmp2 = input_str.split(",");int[] nums = new int[tmp2.length];for (int i = 0; i < tmp2.length; i++) {  nums[i] = Integer.parseInt(tmp2[i]);}return nums;}}

验证：