精准核酸检测 华为OD机试(哎！)

题目描述

为了达到新冠疫情精准防控的需要，为了避免全员核酸检测带来的浪费，需要精准圈定可能被感染的人群。

现在根据传染病流调以及大数据分析，得到了每个人之间在时间、空间上是否存在轨迹的交叉。

现在给定一组确诊人员编号(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

输入： 5 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

输出 3

说明： 编号为1、2号的人员为确诊病例1号与0号有接触，0号与3号有接触，2号54号有接触。所以，需要做核酸检测的人是0号、3

// 寻找可能感染者
void FindPossibleInfects() {
  int numPerson{0};
  // 输入总人数
  std::cin >> numPerson;
  std::cin.ignore();

  // 输入确诊病例人员
  std::string infectsInput;
  std::getline(std::cin, infectsInput);

  // 输入可能感染者
  std::vector<std::string> relationInputs;
  std::string possibleInput;
  for (int i = 0; i < numPerson; i++) {
    std::getline(std::cin, possibleInput);
    relationInputs.emplace_back(possibleInput);
  }

  // 处理输入确诊病例人员
  std::stringstream infectsStream(infectsInput);
  std::string infectsString;
  std::vector<int> infects;
  while (std::getline(infectsStream, infectsString, ',')) {
    infects.emplace_back(std::stoi(infectsString));
  }

  // 处理输入关系矩阵
  using RelationMatrix = std::vector<std::vector<int>>;
  RelationMatrix relationMatrix;
  for (int i = 0; i < numPerson; i++) {
    std::stringstream relationStream(relationInputs[i]);
    std::string relationString;
    std::vector<int> relation;
    while (std::getline(relationStream, relationString, ',')) {
      relation.emplace_back(std::stoi(relationString));
    }
    relationMatrix.emplace_back(relation);
  }

  for (auto infect : infects) {
    // 3表示确诊患者
    relationMatrix[infect][infect] = 3;
  }

  // 遍历可能感染者矩阵，找到可能感染者,注意关系矩阵是对称矩阵，因此只需要处理一半的矩阵元素
  for (int i = 0; i < numPerson; i++) {
    // 只要一行中有一个确诊患者，则该行的接触者就是可能感染者，将其状态设置为2
    for (int j = i; j < numPerson; j++) {
      if (relationMatrix[j][j] == 3 && relationMatrix[i][j] == 1) {
        relationMatrix[i][i] = std::max(relationMatrix[i][i], 2);
        break;
      }
    }

    if (relationMatrix[i][i] > 1) {
      for (int j = i + 1; j < numPerson; j++) {
        // 状态设置为2
        if (relationMatrix[i][j] == 1) {
          relationMatrix[j][j] = std::max(relationMatrix[j][j], 2);
        }
      }
    }
  }

  // 统计可能感染者数量
  int possibleInfectCount{0};
  for (int i = 0; i < numPerson; i++) {
    if (relationMatrix[i][i] == 2) {
      possibleInfectCount++;
    }
  }

  std::cout << possibleInfectCount << std::endl;
}

// 第二种方法，从确诊源头开始，遍历可能感染者
void FindPossibleInfects2() {
  int numPerson{0};
  // 输入总人数
  std::cin >> numPerson;
  std::cin.ignore();

  // 输入确诊病例人员
  std::string infectsInput;
  std::getline(std::cin, infectsInput);

  // 输入可能感染者
  std::vector<std::string> relationInputs;
  std::string possibleInput;
  for (int i = 0; i < numPerson; i++) {
    std::getline(std::cin, possibleInput);
    relationInputs.emplace_back(possibleInput);
  }

  // 处理输入确诊病例人员
  std::stringstream infectsStream(infectsInput);
  std::string infectsString;
  std::vector<int> infects;
  while (std::getline(infectsStream, infectsString, ',')) {
    infects.emplace_back(std::stoi(infectsString));
  }

  // 处理输入关系矩阵
  using RelationMatrix = std::vector<std::vector<int>>;
  RelationMatrix relationMatrix;
  for (int i = 0; i < numPerson; i++) {
    std::stringstream relationStream(relationInputs[i]);
    std::string relationString;
    std::vector<int> relation;
    while (std::getline(relationStream, relationString, ',')) {
      relation.emplace_back(std::stoi(relationString));
    }
    relationMatrix.emplace_back(relation);
  }

  // 从确诊源头开始，遍历可能感染者
  std::set<int> possibleInfects;
  for (auto infect : infects) {
    for (int i = 0; i < numPerson; i++) {
      if (infect != i && relationMatrix[infect][i] == 1) {
        possibleInfects.emplace(i);
      }
    }
  }

  // 可能感染者染者继续传播
  for (auto possible : possibleInfects) {
    for (int i = possible + 1; i < numPerson; i++) {
      if (relationMatrix[possible][i] == 1) {
        possibleInfects.emplace(i);
      }
    }
  }

  // 排除确诊患者
  for (auto infect : infects) {
    possibleInfects.erase(infect);
  }

  // 统计可能感染者数量
  std::cout << possibleInfects.size() << std::endl;
}