当前位置：首页 > article >正文

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

article 2025/2/3 12:29:57

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

输出样例

数据范围

座位横向和纵向最多 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];
    // 将初始感染者加入队列，感染时间设为 0
    queue.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) {
            // 若某些人无法被感染，则返回 -1
            if  (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 here
    std::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;
}