62.病毒在封闭空间中的传播时间|Marscode AI刷题

1.题目

问题描述

在一个封闭的房间里摆满了座位，每个座位东西向和南北向都有固定 1 米的间隔。座位上坐满了人，坐着的人可能带了口罩，也可能没有带口罩。我们已经知道房间里的某个人已经感染了病毒，病毒的传播速度是每秒钟感染距离 1 米，但是超出 1 米病毒没有感染效力。病毒对于戴口罩的人需要两秒钟，或者一秒内被周围的两个人分别感染一次，才能被病毒感染。请实现一个算法，计算出来在给定的人员戴口罩情况，以及已经感染的人员位置情况下，病毒感染屋内所有人所需的时间。假定，已经感染的人戴和不戴口罩都具有相同的感染能力。

输入格式

第一行两个整数 n, m，表示座位有 n 行 m 列

接下来 n 行，每行 m 个整数 T(i, j)表示座位上的人戴口罩情况，0 表示未戴口罩，1 表示戴了口罩

最后一行两个整数 x, y 表示已经感染病毒的人所在座位

输出格式

输出一个整数表示病毒感染屋内所有人所需的时间

输入样例

4 4

0 1 1 1

1 0 1 0

1 1 1 1

0 0 0 1

2 2

输出样例

6

数据范围

座位横向和纵向最多 255

2.思路

1. 初始化

• 定义方向数组用于遍历相邻位置。
• 准备队列用于 BFS 遍历，队列元素包含位置和感染时间。
• 构建感染时间矩阵，初始化为无穷大，记录各位置最早感染时间。
• 确定初始感染者位置，将其加入队列，感染时间设为 0。

2. 广度优先搜索（BFS）

• 从队列取出元素，代表当前感染位置和时间。
• 遍历其四个相邻位置，检查是否在矩阵内。
• 根据相邻位置的人是否戴口罩，计算新的感染时间：
  • 未戴口罩，感染时间加 1 秒。
  • 戴口罩，通常感染时间加 2 秒，若被两个不同方向感染者同时感染，感染时间减为加 1 秒。
• 若新感染时间更小，更新感染时间矩阵并将该位置入队。

3. 结果计算与判断

• 遍历感染时间矩阵：
  • 若有位置感染时间仍为无穷大，说明无法感染，返回 -1。
  • 找出最大感染时间并返回。

3.代码

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <tuple>
using namespace std;int solution(int row_n, int column_m, std::vector<std::vector<int>> seats, std::vector<int> patient) {// Please write your code here// 定义四个方向：右、下、左、上vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 使用队列进行广度优先搜索（BFS），存放的是一个 三元组 (行号, 列号, 时间)queue<tuple<int, int, int>> queue;// 记录每个位置被感染的最早时间，初始设为无穷大vector<vector<int>> infected_time(row_n, vector<int>(column_m, numeric_limits<int>::max()));// 获取初始感染者的位置int start_row = patient[0];int start_col = patient[1];// 将初始感染者加入队列，感染时间设为 0queue.push({start_row, start_col, 0});infected_time[start_row][start_col] = 0;// 进行 BFS 遍历while(!queue.empty()) {auto [r, c, time] = queue.front();queue.pop();// 遍历四个方向for (auto [dr, dc] : directions) {int nr = r + dr;int nc = c + dc;// 检查边界if (0 <= nr && nr < row_n && 0 <= nc && nc < column_m) {int new_time;if (seats[nr][nc] == 0) { // 未带口罩new_time = time + 1;} else { // 戴口罩new_time = time + 2;int adjacent_infected = 0;// 计算周围已感染的邻居数量for (auto [dr2, dc2] : directions) {int ar = nr + dr2;int ac = nc + dc2;if (0 <= ar && ar < row_n && 0 <= ac && ac < column_m && infected_time[ar][ac] == time) {adjacent_infected += 1;}}// 若被两个不同方向的感染者感染，则感染时间减少到 1 秒if (adjacent_infected >= 2) {new_time = min(new_time, time + 1);}}// 只有当新感染时间比当前已记录的感染时间更小时，才更新并入队if (new_time < infected_time[nr][nc]) {infected_time[nr][nc] = new_time;queue.push({nr, nc, new_time});}}}}// 计算最晚感染的时间int max_time = 0;for (int r = 0; r < row_n; ++r) {for (int c = 0; c < column_m; ++c) {// 若某些人无法被感染，则返回 -1if  (infected_time[r][c] == numeric_limits<int>::max()) {return - 1;}max_time = max(max_time, infected_time[r][c]);}}return max_time;
}
int main() {//  You can add more test cases herestd::vector<std::vector<int>> testSeats1 = {{0,1,1,1},{1,0,1,0},{1,1,1,1},{0,0,0,1}};std::vector<std::vector<int>> testSeats2 = {{0,1,1,1},{1,0,1,0},{1,1,1,1},{0,0,0,1}};std::vector<std::vector<int>> testSeats3 = {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};std::vector<std::vector<int>> testSeats4 = {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};std::vector<std::vector<int>> testSeats5 = {{1}};std::cout << (solution(4, 4, testSeats1, {2, 2}) == 6) << std::endl;std::cout << (solution(4, 4, testSeats2, {2, 5}) == 0) << std::endl;std::cout << (solution(4, 4, testSeats3, {2, 2}) == 4) << std::endl;std::cout << (solution(4, 4, testSeats4, {2, 2}) == 6) << std::endl;std::cout << (solution(1, 1, testSeats5, {0, 0}) == 0) << std::endl;return 0;
}

4.参考资料

AI刷题-病毒在封闭空间中的传播时间-CSDN博客