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

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

article 2025/1/21 16:12:11

目录

问题描述

输入格式

输出格式

解题思路：

问题理解

数据结构选择

算法步骤

代码实现： 

1.初始化： 

2.设置边界条件： 

3.判断 

4.更新： 

 5.返回

 最终的实现代码如下：

运行结果： 

 

以后我想试着一篇博客就写一道题解，尽可能的地把题解思路讲清楚（ps：因为我昨天看之前写的题解的时候有点云里雾里，这就违背我写题解的初衷了）

问题描述

在一个封闭的房间里摆满了座位，每个座位东西向和南北向都有固定 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

解题思路：

问题理解

  1. 房间布局：房间是一个 n x m 的二维网格，每个格子代表一个座位。
  2. 口罩情况：每个座位上的人可能有口罩（1）或没有口罩（0）。
  3. 病毒传播规则：
    • 病毒每秒可以传播到距离为1米的座位。
    • 未戴口罩的人（0）在1秒内被感染。
    • 戴口罩的人（1）需要2秒或被周围的两个人分别感染一次才能被感染。
  4. 初始感染者：给定一个初始感染者的位置 (x, y)。

数据结构选择

  1. 二维数组：用于表示房间的座位布局和每个人的口罩情况。
  2. 队列：用于广度优先搜索（BFS），记录当前时间步内需要处理的感染者。
  3. 时间记录：用于记录每个座位被感染的时间。

算法步骤

  1. 初始化：

    • 创建一个二维数组 time 记录每个座位被感染的时间，初始值为 -1 表示未被感染。
    • 将初始感染者的位置 (x, y) 加入队列，并设置 time[x][y] = 0。

  2. 广度优先搜索（BFS）：

    • 从队列中取出当前时间步的感染者。
    • 检查其四个方向（上、下、左、右）的邻居：
      • 如果邻居未被感染且未戴口罩（0），则将其感染时间设置为当前时间步加1，并加入队列。
      • 如果邻居未被感染且戴口罩（1），则需要特殊处理：
        • 如果当前时间步加1等于2秒，或者当前时间步加1等于1秒且有两个邻居已经感染，则将其感染时间设置为当前时间步加1，并加入队列。

  3. 终止条件：

    • 当队列为空时，表示所有可能被感染的座位都已经被处理。

  4. 结果输出：

    • 返回 time 数组中的最大值，即为病毒感染屋内所有人所需的时间。

代码实现： 

1.初始化： 

我们单独创建directions作为四个方向的偏移量，queue作为bfs算法的队列，infected_time作为时间数组记录当前病人感染时间

同时获取被感染人的坐标，插入队列，并将时间轴设为0；

std::vector<std::pair<int, int>> directions = {
  
  {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
std::queue<std::tuple<int, int, int>> queue;
std::vector<std::vector<int>> infected_time(row_n, std::vector<int>(column_m, std::numeric_limits<int>::max()));

int start_row = patient[0];
int start_col = patient[1];
queue.push({start_row, start_col, 0});  // (行, 列, 时间)
infected_time[start_row][start_col] = 0;

2.设置边界条件： 

0 <= nr && nr < row_n && 0 <= nc && nc < column_m 

3.判断 

 如果此时该坐标的人未带口罩，则seats[nr][nc] == 0，反之则是戴口罩，对此有两种不同的判定：

对于前者：只需将时间数组自增便感染成功

对于后者：需要对当前时间进行2秒的自增，然后判断当前位置的周围是否有大于等于2的感染者，

此时如果满足该条件，则进行特殊处理，即当前位置的病人需要比较是前面自增两秒的的感染时间少还是存在两名以上感染者感染他的时间少。 不过我这是觉得直接处理成time+1就行了，应该是必定大于前者的

                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;
                        }
                    }
                    if (adjacent_infected >= 2) {
                        new_time = std::min(new_time, time + 1);
                    }
                }

4.更新： 

此时对当前的时间与当前位置原本的时间（或未感染）进行 比较：

        当小于时，便需要将原本写入的时间更新为此时更短实现感染完成的时间，同时插入到队列中，进行下一轮循环

            if (new_time < infected_time[nr][nc]) {
                    infected_time[nr][nc] = new_time;
                    queue.push({nr, nc, new_time});
                }

 5.返回

也就是遍历，一旦发现有未感染的则返回-1说明无法达成题目要求 

    int max_time = 0;
    for (int r = 0; r < row_n; ++r) {
        for (int c = 0; c < column_m; ++c) {
            if (infected_time[r][c] == std::numeric_limits<int>::max()) {
                return -1;  // 表示有些人无法感染
            }
            max_time = std::max(max_time, infected_time[r][c]);
        }
    }

 最终的实现代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

int solution(int row_n, int column_m, std::vector<std::vector<int>> seats, std::vector<int> patient) {
    std::vector<std::pair<int, int>> directions = {
  
  {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    std::queue<std::tuple<int, int, int>> queue;
    std::vector<std::vector<int>> infected_time(row_n, std::vector<int>(column_m, std::numeric_limits<int>::max()));

    int start_row = patient[0];
    int start_col = patient[1];
    queue.push({start_row, start_col, 0});  // (行, 列, 时间)
    infected_time[start_row][start_col] = 0;

    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;
                        }
                    }
                    if (adjacent_infected >= 2) {
                        new_time = std::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) {
            if (infected_time[r][c] == std::numeric_limits<int>::max()) {
                return -1;  // 表示有些人无法感染
            }
            max_time = std::max(max_time, infected_time[r][c]);
        }
    }

    return max_time;
}


int main() {
    // 你可以添加更多测试用例
    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;
}

运行结果： 

 

 

 

 

 


http://www.kler.cn/a/512292.html

相关文章：

  • SDL2：Android APP编译使用 -- SDL2多媒体库使用音频实例
  • C 语言雏启：擘画代码乾坤，谛观编程奥宇之初瞰
  • TongESB7.1.0.0如何使用dockercompose运行镜像（by lqw）
  • leetcode 面试经典 150 题：合并区间
  • 51c自动驾驶~合集48
  • 用户中心项目教程（五）---MyBatis-Plus完成后端初始化+测试方法
  • 企业级流程架构设计思路-基于价值链的流程架构
  • 数据结构(二)栈/队列和二叉树/堆
  • centos虚拟机异常关闭，导致数据出现问题
  • 【2024年度个人生活与博客事业的融合与平衡总结】
  • 深入解析 C++17 中的 u8 字符字面量：提升 Unicode 处理能力
  • 大模型LLM-微调 RAG
  • Java-数据结构-二叉树习题(1)
  • AUTOSAR OS模块详解(三) Alarm
  • 我想通过python语言，学习数据结构和算法该如何入手？
  • 低代码运维与管理服务
  • 大数据学习(37)- Flink运行时架构
  • 嵌入式STM32创新教学：华清远见虚拟仿真实验平台与智能车项目师资培训
  • Zemax STAR 模块的入门设置
  • 《数字图像处理（面向新工科的电工电子信息基础课程系列教材）》重印变更的彩插
  • Linux(Centos 7.6)命令详解：iconv
  • matlab中的griddata函数
  • element表格滚动错位问题，使用uniapp写的项目
  • 基于Web实时通信的无人机载物联网与严格时间敏感性：案例研究
  • 力扣刷题心得_JAVA
  • 鸿蒙系统 将工程HarmonyOS变成OpenHarmony