网站后台进不去的原因,小程序开发公司文案,网站开发项目实战,临沂做网站公司哪家好1.题目
问题描述
在一个封闭的房间里摆满了座位#xff0c;每个座位东西向和南北向都有固定 1 米的间隔。座位上坐满了人#xff0c;坐着的人可能带了口罩#xff0c;也可能没有带口罩。我们已经知道房间里的某个人已经感染了病毒#xff0c;病毒的传播速度是每秒钟感染距…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::vectorstd::vectorint seats, std::vectorint patient) {// Please write your code here// 定义四个方向右、下、左、上vectorpairint, int directions {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 使用队列进行广度优先搜索BFS存放的是一个 三元组 (行号, 列号, 时间)queuetupleint, int, int queue;// 记录每个位置被感染的最早时间初始设为无穷大vectorvectorint infected_time(row_n, vectorint(column_m, numeric_limitsint::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_limitsint::max()) {return - 1;}max_time max(max_time, infected_time[r][c]);}}return max_time;
}
int main() {// You can add more test cases herestd::vectorstd::vectorint testSeats1 {{0,1,1,1},{1,0,1,0},{1,1,1,1},{0,0,0,1}};std::vectorstd::vectorint testSeats2 {{0,1,1,1},{1,0,1,0},{1,1,1,1},{0,0,0,1}};std::vectorstd::vectorint testSeats3 {{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};std::vectorstd::vectorint testSeats4 {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};std::vectorstd::vectorint 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博客
