题面解释:

在一个$M*N$的地图中，包含墙体、空地、已感染和未感染的人（分别戴或不戴口罩）。病毒的传播模型需要根据感染者的危险系数（戴口罩与否影响系数大小）来计算传播轨迹，危险系数会随距离衰减，且被墙体阻隔。未感染的人若所处位置的危险系数大于等于其感染阈值，则会在第二天被感染，并影响周围区域。输入包括地图尺寸$M$和$N$，以及戴口罩和不戴口罩的危险系数和感染阈值，接着是地图数据。输出为每个格子的状态：如果是空地或墙体，输出$-1$；如果初始已感染，输出$0$；如果被感染，输出被感染的天数；否则输出$-1$。

多轮 多源bfs

我们不难发现，整个过程就是，每天会有若干个新增的感染人数。每次对新增的感染人数，我们更新危险系数矩阵。然后对于更新后的危险系数矩阵，我们再检查新增感染，如此往复。

所以思路是：

1.最开始将第0天就感染的人放入一个队列，我们称作增广队列。

2.对增广队列进行一个bfs过程，每次取出与队头属于同一天被感染的人

3.对这些人，进行一个多源bfs:同时放入感染队列，以bfs的形式更新危险系数矩阵。

4.结束完3之后，对于新的危险系数矩阵，我们再次进行检查新增感染人数，然后再次放入增广队列。

基本思路：

1. 初始状态的处理：

   • 我们首先遍历整个地图，找到所有初始已感染的格子（包括戴口罩和不戴口罩的已感染人群），将这些感染源加入一个队列（增广队列），并初始化它们的危险系数矩阵。
   • 对于墙体、空地等不参与传播的格子，我们直接设置输出为-1，表示这些格子不会被感染。

2. BFS搜索过程：

   • 在每一天，我们从增广队列中取出所有的感染源，并从这些感染源出发，通过BFS来传播危险系数。每次传播时，考虑四个方向（上、下、左、右），并根据不同的格子状态（墙体、空地、是否戴口罩）来更新周围的危险系数。
   • 对于一个未感染的人，如果他所在位置的危险系数超过了其感染阈值，则该人会在第二天被感染。

3. 多源BFS的实现：

   • 当我们找到一个新的感染源时，立刻将其加入队列，并再次进行BFS，更新整个危险系数矩阵，确保病毒从多个感染源同时向外传播。

4. 停止条件：

   • 当队列为空，即所有可能被感染的人都已传播完毕，或者无法再传播时，停止模拟，输出结果。

5. 输出结果：

   • 对于每个格子，如果它最终没有被感染，输出-1；如果被感染，则输出感染发生的天数；对于初始感染的格子，输出0。

代码如下

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX = 105;
int r, c, d1, d2, t1, t2;
int grid[MAX][MAX], danger[MAX][MAX], res[MAX][MAX];
int dx[4] = {1, -1, 0, 0};  // 四个方向：上、下、左、右
int dy[4] = {0, 0, 1, -1};  // 对应的Y轴变化

// 定义节点结构体，用于存储坐标
struct Node {
    int x, y;
};

// 执行广度优先搜索
vector<Node> bfs(queue<Node> &q) {
    vector<Node> newInfected; // 用于存储新增感染的人
    while (!q.empty()) {  // 当队列不为空时，执行BFS
        Node cur = q.front(); // 取出当前队列的队头
        q.pop(); // 从队列中删除当前节点
        int x = cur.x, y = cur.y;

        // 对四个方向进行BFS
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];

            // 检查边界条件和是否可以传播（不是墙、空地且传播危险系数减1）
            if (nx >= 0 && nx < r && ny >= 0 && ny < c && grid[nx][ny] != 1 && danger[nx][ny] < danger[x][y] - 1) {
                danger[nx][ny] = danger[x][y] - 1; // 更新新的危险系数

                // 判断是否会感染人：未感染人被危险系数超过阈值感染
                if ((danger[nx][ny] >= t1 && grid[nx][ny] == 5) ||  // 未感染戴口罩
                    (danger[nx][ny] >= t2 && grid[nx][ny] == 4)) {  // 未感染不戴口罩
                    newInfected.push_back({nx, ny});  // 将感染的人加入新增感染列表
                }

                q.push({nx, ny});  // 将该位置放入队列继续传播
            }
        }
    }
    return newInfected; // 返回新增感染列表
}

int main() {
    cin >> r >> c >> d1 >> d2 >> t1 >> t2; // 读取输入参数
    queue<Node> q;  // 初始化增广队列

    // 初始化输入数据
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> grid[i][j];  // 读取地图数据
            if (grid[i][j] == 2 || grid[i][j] == 3) {  // 初始已感染的人
                danger[i][j] = (grid[i][j] == 3) ? d1 : d2;  // 根据是否戴口罩设置初始危险系数
                q.push({i, j});  // 加入队列
                res[i][j] = 0;  // 这些人已经感染，设置结果为0
            } else {
                res[i][j] = -1;  // 对于墙、空地等，设置为-1
            }
        }
    }

    int days = 0;  // 记录天数
    while (!q.empty()) {
        days++;  // 每次BFS过程代表经过一天
        vector<Node> newInfected = bfs(q);  // 进行BFS，返回新增感染的人

        // 处理新增感染者
        for (Node n : newInfected) {
            int x = n.x, y = n.y;
            res[x][y] = days;  // 设置感染天数

            // 根据类型更新危险系数
            if ((grid[x][y] == 4 && danger[x][y] < d2) ||  // 更新不戴口罩感染者的危险系数
                (grid[x][y] == 5 && danger[x][y] < d1)) {  // 更新戴口罩感染者的危险系数
                danger[x][y] = (grid[x][y] == 4) ? d2 : d1;  // 更新该位置危险系数
                q.push({x, y});  // 加入队列
            }

            grid[x][y] -= 2;  // 更新地图，将未感染的状态变为已感染
        }
    }

    // 输出最终结果
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cout << res[i][j] << " ";  // 输出每个格子的结果
        }
        cout << endl;
    }
    return 0;
}

Python

M , N , a1 , a2 , b1 , b2 = map(int, input().split())

mp = [list(map(int, input().split())) for i in range(M)]

#危险系数
danger = [[0 for i in range(N)] for j in range(M)]

res = [[-1 for i in range(N)] for j in range(M)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
# 传播危险系数函数
def spread(start_points):
    global danger , mp
    q = []
    for x , y in start_points:
        q.append((x, y))
        # 不带口罩
        if mp[x][y] == 2 or mp[x][y] == 4:
            danger[x][y] = a2
        elif mp[x][y] == 3 or mp[x][y] == 5:
            danger[x][y] = a1
    while q:
        x, y = q.pop(0)
        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]
            if tx >= 0 and tx < M and ty >= 0 and ty < N and mp[tx][ty] != 1 and danger[tx][ty] < danger[x][y] - 1:
                danger[tx][ty] = danger[x][y] - 1
                q.append((tx, ty))
                
q = []
for i in range(M):
    for j in range(N):
        if mp[i][j] == 2:
            q.append((i, j , 0))
            res[i][j] = 0
        elif mp[i][j] == 3:
            q.append((i, j , 0))
            res[i][j] = 0
while q:
    x , y , day = q.pop(0)
    # 由于一个点一个点的bfs会导致超时，所以我们一次性拿出所有的day相同的点，然后一次性处理：多源bfs
    arr = [[x , y]]
    while q and q[0][2] == day:
        x , y , _  = q.pop(0)
        arr.append([x , y])
    # 传播危险系数(更新danger矩阵)
    spread(arr)
    # 检查是否有新人被感染
    for i in range(M):
        for j in range(N):
            # 感染阈值
            infect_num = 0
            if mp[i][j] == 4:
                infect_num = b2
            elif mp[i][j] == 5:
                infect_num = b1
            # 有人并且该位置尚未被计算
            if infect_num != 0 and res[i][j] == -1:
                if danger[i][j] >= infect_num:
                    q.append((i , j , day + 1))
                    res[i][j] = day + 1



# 输出答案
for i in range(M):
    for j in range(N):
        print(res[i][j], end = " ")
    print()

Java

import java.util.*;

public class Main {
    static int[][] grid;
    static int[][] danger;
    static int[][] res;
    // static final int MX = 105;
    static int m,n, a1, a2, b1, b2;
    static final int[][] DIRECTIONS = new int[][]{
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}
    };

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读入行列
        m = in.nextInt();
        n = in.nextInt();
        grid = new int[m][n];
        danger = new int[m][n];
        res = new int[m][n];
        // 读入危险系数
        a1 = in.nextInt();
        a2 = in.nextInt();
        b1 = in.nextInt();
        b2 = in.nextInt();
        //in.nextLine();
        Deque<int[]> dQueue = new LinkedList<>();
        Deque<int[]> hQueue = new LinkedList<>();
        // 初始化
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = in.nextInt();
                // 已感染 进入已感染队列
                if (grid[i][j] == 2 || grid[i][j] == 3) {
                    danger[i][j] = (grid[i][j]==3)? a1:a2;
                    res[i][j] = 0;
                    dQueue.addLast(new int[]{i, j});
                }else{
                    res[i][j] = -1;
                }
                // 没感染 加到健康队列
                if (grid[i][j]==4 || grid[i][j]==5){
                    hQueue.addLast(new int[]{i,j});
                }
            }
        }
        // 更新危险系数
        update(dQueue);
        int pre = 0;             // 上一轮健康队列长度
        int now = hQueue.size(); // 当前健康队列长度
        int daysCount = 0;
        // bfs pre!=now说明有新的感染，如果一直没有新的感染说明所有可能被感染的人已经被感染。循环终止
        while (pre!=now) {
            daysCount++;
            pre = now;
            for(int i=0;i<pre;i++){
                int[] cur_pos = hQueue.pollFirst();
                int x = cur_pos[0];
                int y = cur_pos[1];
                // 检查本轮是否会由于上一轮的状态被感染
                if(grid[x][y] == 4){
                    if(danger[x][y]>=b2){
                        res[x][y] = daysCount;
                        // 感染后更新健康情况
                        if(danger[x][y]<a2){
                            danger[x][y] = a2;
                            dQueue.addLast(new int[]{x,y});
                        }
                    }
                    // 未感染
                    else {
                        hQueue.addLast(new int[]{x,y});
                    }
                }else if(grid[x][y]==5){
                    if(danger[x][y]>=b1){
                        res[x][y] = daysCount;
                        if(danger[x][y]<a1){
                            danger[x][y] = a1;
                            dQueue.addLast(new int[]{x,y});
                        }
                    }else {
                        hQueue.addLast(new int[]{x,y});
                    }
                }
            }
            // 每层遍历完 更新一次危险系数
            update(dQueue);
            now = hQueue.size();
        }

        // 输出结果
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                System.out.print(res[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static void update(Deque<int[]> queue){
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                int[] cur_pos = queue.pollFirst();
                int x = cur_pos[0];
                int y = cur_pos[1];
                for(int[] d: DIRECTIONS){
                    int dx = x+d[0];
                    int dy = y+d[1];
                    // 位置合法
                    if(dx>=0 && dx<grid.length && dy>=0 && dy<grid[0].length && grid[dx][dy]!=1){
                        // 更新危险系数
                        if (danger[x][y]-1>danger[dx][dy]){
                            danger[dx][dy] = danger[x][y]-1;
                            queue.addLast(new int[]{dx,dy});
                        }
                    }
                }

            }
        }
    }
}

题目内容

最近病毒肆虐，科学家为了研究病毒的传播轨迹，需要设计一套简易的传播模型。

在一张$M*N$地图中，包含墙体，空地，已感染的人(不戴口罩)，已感染的人(戴口罩)，未感染的人(不戴口罩)，未感染的人(戴口罩)。科学家会设置一些危险系数，以及感染阈值。然后观察未感染人群大概多少天以后会被感染。

位置含义的编码如下:

危险系数:为感染的人对周围的位置造成的风险(戴口罩和不戴口罩数值不同)，每过一格，危险系数就减$1$。遇到墙体则不再进行传播。一个位置上如果出现多个传染源传播的危险系数，则危险系数使用多个危险系数的最大值。

感染阈值:为该位置的人被感染的门限(戴口罩和不戴口罩数值不同)，当危险系数大于等于感染阈值，则该位置的人就会被传染。 注意:

$1$.判断当前位置是否感染只有一个条件，就是当前位置上的危险系数是否大于等于当前位置上的人的感染阈值。是否带口罩会影响危险系数和感染阈值的大小，从而间接的影响该位置的人是否会被感染。

$2$.未感染的人在感染后会在第二天变成已感染的人，比如未感染的人(戴口罩) 如果在第$3$天发现自己的感染阈值小于危险系数(也就是会被感染)，那么在第$4$天该位置就会变成已感染的人(戴口罩).所以在第$4$天以后需要将该位置以及周围的危险系数刷新，这就有可能会感染其他更多的人。

输入描述

第一行: $M, N, a1, a2,b1, b2$用空格隔开，参数具体含义如下:

第二行到第$M+2$行:$M$行$N$列地图数据信息

输出描述

输出$M$行$N$列数据信息，每个位置需要输出的内容如下:

• 该位置没有人(空地或者墙壁)的话则返回$-1$
• 该位置的人初始态时就被感染了的话，则填$0$
• 该位置的人初始没有被感染，但是最终被感染，则填被感染的天数
• 该位置的人没有被感染，则返回$-1$

样例1

输入

3 4 7 10 6 2
0 0 0 0
2 0 1 5
0 0 0 0

输出

-1 -1 -1 -1
0 -1 -1 -1 
-1 -1 -1 -1

说明

该用例中，初始地图中，第$2$行第$1$列处存在一个已感染并且不戴口罩的人，根据危险系数的配置信息，危险系数(不戴口罩)为$10$，所以该位置的危险系数为$10$，计算所有位置的危险系数如下:

可以看到因为墙的原因，第$2$行第$4$列位置上的危险系数为$5$，该位置上的人戴了口罩，该位置上的人感染阈值为$6$，则该人不会被感染。

样例2

输入

3 4 7 10 6 2
0 0 0 0
2 0 1 5
0 0 0 5

输出

-1 -1 -1 -1
0 -1 -1 2
-1 -1 -1 1

说明

该样例中，初始地图中，第$2$行第$1$列处存在一个已感染并且不戴口罩的人，根据危险系数的配置信息，危险系数(不戴口罩)为$10$，所以该位置的危险系数为$10$，计算所有位置的危险系数如下：

第$2$行第$4$列位置上的危险系数为$5$，该位置上的人戴了口罩，该位置上的人感染阈值为$6$，则该人在第一天不会被感染，

第$3$行第$4$列位置上的危险系数为$6$，该位置上的人戴了口罩，该位置上的人感染阈值为$6$，则该人在第一天会被感染。感染后该人会变成已感染的人(戴口罩)

第一天以后地图更新如下: $0\ 0\ 0\ 0$ $2\ 0\ 1\ 5$ $0\ 0\ 0\ 3$

这时再计算第二天的危险系数，根据危险系数的配置信息，危险系数(戴口罩)为$7$，所以第$3$行第$4$列位置的危险系数为$7$，所有位置需要计算危险系数的最大值，如下图:

第二天，第$2$行第$4$列位置上的危险系数从$5$提升到了$6$，而该位置上的人感染阈值为$6$，则该位置的人会在第二天被感染。 最终结果如下:

$-1\ -1\ -1\ -1$

$0\ -1\ -1\ 2$

$-1\ -1\ -1\ 1$