华为od机试100分题-精准核酸检测
方法不一定效率高,但一般比较好理解。
题目:
思路与解析:
1、用一个数组存储是否访问过,避免重复访问;
2、输入已经感染的人,将其存放到栈,将其视为访问过;
3、输入矩阵,用vector存储;
4、对栈中每个元素,遍历其对应行,看是否有未访问且传染的人,有的话count++(初始为0,统计传染人数);
5、输出count,即有多少人要做核酸检测。
#include <iostream> #include<vector> #include<stack> using namespace std; int main() { int n; cin >> n; stack<int> s; vector<int> yn(n,0); vector<vector<int>> matrix(n,vector<int>(n)); int num; while (cin >> num) { s.push(num); yn[num] =1; if (cin.peek() == '\n') break; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cin >> matrix[i][j]; } int count = 0; while (!s.empty()) { int i = s.top(); s.pop(); for (int j = 0; j < n; j++) { if (yn[j] == 0 && matrix[i][j] == 1) { yn[j] = 1; s.push(j); count++; } } } cout << count << endl; }