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

devtools/2025/1/21 11:19:01/

目录

问题描述

输入格式

输出格式

解题思路：

问题理解

数据结构选择

算法步骤

代码实现： 

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.ppmy.cn/devtools/152333.html

相关文章

vmware17.5 - 解决ubuntu长按按键会导致图形界面卡死的情况

vmware17.5 - 解决ubuntu长按按键会导致图形界面卡死的情况

在vmware上安装的ubuntu一直存在一个问题&#xff0c;长按按键会导致ubuntu图形界面卡死&#xff0c;不能自己恢复&#xff0c;只能关机重启&#xff0c;而且每次都能复现。搞得每次敲代码&#xff0c;动不动就卡死&#xff0c;重启后说不定还会丢代码&#xff0c;真服了。 以…
阅读更多...
＜ OS 有关 ＞ 阿里云：轻量应用服务器 的使用 安装 Tailscale 后DNS 出错， 修复并替换 apt 数据源

＜ OS 有关 ＞ 阿里云：轻量应用服务器 的使用 安装 Tailscale 后DNS 出错， 修复并替换 apt 数据源

VPS 配置 主机&#xff1a;vCPU x2, 512MB, 20GB位置&#xff1a;阿里云&#xff0c;日本.东京OS&#xff1a; ubuntu24.20 原因&#xff1a; 这篇是操作过程的记录文章。 2 个月前&#xff0c; 在阿里云买了台 vps 。当时本想放到韩国&#xff0c;因为它离北京近。 但最便…
阅读更多...
BERT和Transformer模型有什么区别

BERT和Transformer模型有什么区别

BERT&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;和Transformer都是自然语言处理&#xff08;NLP&#xff09;领域的重要模型&#xff0c;它们之间的区别主要体现在以下几个方面&#xff1a; 模型定位 Transformer&#xff1a;严格来说并…
阅读更多...
Node进行版本切换，如何使用 nvm 轻松切换 node 版本

Node进行版本切换，如何使用 nvm 轻松切换 node 版本

有时候我们需要启动各种版本的项目&#xff0c;但是每个项目需要使用不同的 node 版本才能正常运行。所以我们需要随时切换 node 版本来启动项目&#xff0c;故我们需要使用到 nvm。 nvm 可以 轻松控制 Node版本切换。 查看已安装的Node版本nvm list切换Node版本(以12.22.12版…
阅读更多...
#CSS 实用属性总结

#CSS 实用属性总结

文章目录 防脱发神器颜色的 Alpha 通道尺寸的百分比最大最小宽高伪类选择器contenteditable 属性table 元素CSS中的大小/长度单位绝对单位相对单位与字体大小相关与视窗大小相关百分比单位动态计算单位 时间单位角度单位分辨率单位使用建议 防脱发神器 为了更直观地控制元素尺…
阅读更多...
深入理解Linux系统内存中文件结构以及缓冲区，模拟实现c语言库文件接口

深入理解Linux系统内存中文件结构以及缓冲区，模拟实现c语言库文件接口

目录 一、文件的理解 二、文件操作 1.Linux系统中文件接口&#xff1a; 1.1.open 1.2.write 1.3.read 三、文件描述符 四、重定向的理解 五、缓冲区 1.语言层缓冲区 2.系统层缓冲区 3.缓冲区刷新策略&#xff08;语言层&#xff09; 六、c文件接口的模拟实现 1.m…
阅读更多...
C# OpenCV机器视觉:区域生长算法

C# OpenCV机器视觉:区域生长算法

在一个月黑风高的夜晚&#xff0c;阿强猫在他那乱得像被打劫过的实验室里&#xff0c;四周堆满了各种奇奇怪怪的电路板、闪烁的指示灯和缠绕成一团的电线&#xff0c;活脱脱一个疯狂科学家的秘密基地。窗外&#xff0c;狂风呼啸着拍打着窗户&#xff0c;仿佛在催促着阿强&#…
阅读更多...
（7）(7.2) 围栏

（7）(7.2) 围栏

文章目录 前言 1 通用设置 2 围栏类型 3 破坏栅栏行动 4 使用 RC 通道辅助开关启用栅栏 5 自动高度规避 6 在任务规划器中启用围栏 7 用于遥控飞行训练 8 MAVLink 支持 前言 ArduPilot 支持基于本机的圆柱形&#xff08;“TinCan”&#xff09;和多边形和/或圆柱形、…
阅读更多...
最新文章

Copyright @ 2022~2023