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];
// 将初始感染者加入队列，感染时间设为 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;
}
4.参考资料
AI刷题-病毒在封闭空间中的传播时间-CSDN博客
