目录
以后我想试着一篇博客就写一道题解，尽可能的地把题解思路讲清楚（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
解题思路：
问题理解
- 房间布局：房间是一个
n x m的二维网格，每个格子代表一个座位。 - 口罩情况：每个座位上的人可能有口罩（1）或没有口罩（0）。
- 病毒传播规则：
- 病毒每秒可以传播到距离为1米的座位。
- 未戴口罩的人（0）在1秒内被感染。
- 戴口罩的人（1）需要2秒或被周围的两个人分别感染一次才能被感染。
- 初始感染者：给定一个初始感染者的位置
(x, y)。
数据结构选择
- 二维数组：用于表示房间的座位布局和每个人的口罩情况。
- 队列：用于广度优先搜索（BFS），记录当前时间步内需要处理的感染者。
- 时间记录：用于记录每个座位被感染的时间。
算法步骤
-
初始化：
- 创建一个二维数组
time记录每个座位被感染的时间，初始值为-1表示未被感染。 - 将初始感染者的位置
(x, y)加入队列，并设置time[x][y] = 0。
- 创建一个二维数组
-
广度优先搜索（BFS）：
- 从队列中取出当前时间步的感染者。
- 检查其四个方向（上、下、左、右）的邻居：
- 如果邻居未被感染且未戴口罩（0），则将其感染时间设置为当前时间步加1，并加入队列。
- 如果邻居未被感染且戴口罩（1），则需要特殊处理：
- 如果当前时间步加1等于2秒，或者当前时间步加1等于1秒且有两个邻居已经感染，则将其感染时间设置为当前时间步加1，并加入队列。
-
终止条件：
- 当队列为空时，表示所有可能被感染的座位都已经被处理。
-
结果输出：
- 返回
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;
}运行结果：
