遍历一次地图分别储存健康人员和感染人员的位置; 先依据感染人员更新危险系数图; 再依据新感染者的位置和天数更新危险系数图和健康天数图，直到某天健康人员队列长度不改变为止; 返回健康天数图。

# python
from collections import deque


def main():
    m, n, a1, a2, b1, b2 = map(int, input().split())
    maps = [list(map(int, input().split())) for _ in range(m)]

    directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
    danger = [[0 for _ in range(n)] for _ in range(m)]
    health = [[-1 for _ in range(n)] for _ in range(m)]
    h_que = deque()
    d_que = deque()
    for i in range(m):
        for j in range(n):
            if maps[i][j] == 2:
                danger[i][j] = a2
                health[i][j] = 0
                d_que.append([i, j])
            elif maps[i][j] == 3:
                danger[i][j] = a1
                health[i][j] = 0
                d_que.append([i, j])
            if maps[i][j] == 4 or maps[i][j] == 5:
                h_que.append([i, j])

    def update(que):
        while que:
            cur = que.popleft()
            for dx, dy in directions:
                x = cur[0] + dx
                y = cur[1] + dy
                if 0 <= x < m and 0 <= y < n and maps[x][y] != 1 and danger[cur[0]][cur[1]] - 1 > danger[x][y]:
                    danger[x][y] = danger[cur[0]][cur[1]] - 1
                    que.append([x, y])

    update(d_que)
    pre = 0
    now = len(h_que)
    day = 0
    while pre != now:
        pre = now
        day += 1
        for k in range(pre):
            px, py = h_que.popleft()
            if maps[px][py] == 4:
                if danger[px][py] >= b2:
                    health[px][py] = day
                    if danger[px][py] < a2:
                        danger[px][py] = a2
                        d_que.append([px, py])
                else:
                    h_que.append([px, py])
            elif maps[px][py] == 5:
                if danger[px][py] >= b1:
                    health[px][py] = day
                    if danger[px][py] < a1:
                        danger[px][py] = a1
                        d_que.append([px, py])
                else:
                    h_que.append([px, py])
        update(d_que)
        now = len(h_que)
    for i in range(m):
        print(*health[i])


if __name__ == '__main__':
    main()

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_M = 100;
const int MAX_N = 100;

int M, N, a1, a2, b1, b2;
int Map[MAX_M][MAX_N];
int InfectionDay[MAX_M][MAX_N];
int danger[MAX_M][MAX_N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

struct Position {
    int x, y, danger;
    bool operator<(const Position& other) const {
        return danger < other.danger; // For max-heap
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> M >> N >> a1 >> a2 >> b1 >> b2;

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> Map[i][j];
        }
    }

    memset(InfectionDay, -1, sizeof(InfectionDay));

    int day = 0;
    bool hasNewInfection = true;

    while (hasNewInfection) {
        hasNewInfection = false;

        // Reset danger coefficients
        memset(danger, 0, sizeof(danger));

        // Initialize priority queue with infected positions
        priority_queue<Position> pq;

        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (Map[i][j] == 2 || Map[i][j] == 3) {
                    // Infected person
                    int initial_danger = (Map[i][j] == 2) ? a2 : a1;
                    danger[i][j] = initial_danger;
                    pq.push({i, j, initial_danger});
                }
            }
        }

        // Dijkstra's algorithm
        while (!pq.empty()) {
            Position current = pq.top();
            pq.pop();

            if (current.danger < danger[current.x][current.y]) {
                continue;
            }

            for (int dir = 0; dir < 4; ++dir) {
                int nx = current.x + dx[dir];
                int ny = current.y + dy[dir];

                if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
                if (Map[nx][ny] == 1) continue; // Wall

                int new_danger = current.danger - 1;
                if (new_danger <= 0) continue;

                if (new_danger > danger[nx][ny]) {
                    danger[nx][ny] = new_danger;
                    pq.push({nx, ny, new_danger});
                }
            }
        }

        // Check for new infections
        vector<pair<int, int>> newlyInfected;

        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (Map[i][j] == 4 || Map[i][j] == 5) {
                    // Uninfected person
                    int infection_threshold = (Map[i][j] == 4) ? b2 : b1;
                    if (danger[i][j] >= infection_threshold) {
                        InfectionDay[i][j] = day + 1;
                        newlyInfected.push_back({i, j});
                        hasNewInfection = true;
                    }
                }
            }
        }

        // Update the map with new infections
        for (auto& pos : newlyInfected) {
            int i = pos.first;
            int j = pos.second;
            if (Map[i][j] == 4) {
                Map[i][j] = 2; // Becomes infected not wearing mask
            } else if (Map[i][j] == 5) {
                Map[i][j] = 3; // Becomes infected wearing mask
            }
        }

        day++;
    }

    // Output the results
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (Map[i][j] == 0 || Map[i][j] == 1) {
                cout << -1;
            } else if (InfectionDay[i][j] == -1) {
                if (Map[i][j] == 2 || Map[i][j] == 3) {
                    cout << 0;
                } else {
                    cout << -1;
                }
            } else {
                cout << InfectionDay[i][j];
            }
            if (j != N - 1) cout << " ";
        }
        cout << endl;
    }

    return 0;
}

题面解释:

在一个$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});
                        }
                    }
                }

            }
        }
    }
}

#map 0:空地, 1:墙壁, 2:感染(不带口罩), 3:感染(带口罩), 4:未感染(不带口罩), 5:未感染(带口罩)
#out -1:空地/墙壁/没感染, 0: 初始态感染, n:后期被感染，被感染天数
#dan a1:危险系数(带口罩)， a2:危险系数(不带口罩), b1:感染阈值(带口罩), b2:感染阈值(不带口罩)

# BFS
from collections import deque

m, n, a1, a2, b1, b2 = map(int, input().split())
d_m = [[0 for _ in range(n)] for _ in range(m)]
map_m = [list(map(int, input().split())) for _ in range(m)]
out_m = [[-1 for _ in range(n)] for _ in range(m)]

count = 0

while True:
    start = []

    for i in range(m):
        for j in range(n):
            if map_m[i][j] == 2:
                d_m[i][j] = a2
                if out_m[i][j] == -1:
                    out_m[i][j] = count
                    start.append((i, j, a2))
            elif map_m[i][j] == 3:
                d_m[i][j] = a1
                if out_m[i][j] == -1:
                    out_m[i][j] = count
                    start.append((i, j, a1))
            if map_m[i][j] == 1:
                d_m[i][j] = -1

    def bfs(graph, start):
        queue = deque(start)
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        while queue:
            x, y, dangerous = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and d_m[nx][ny] != -1 and dangerous - 1 > d_m[nx][ny]:
                    d_m[nx][ny] = dangerous - 1
                    queue.append((nx, ny ,dangerous - 1))

    bfs(d_m, start)
    
    t = 1
    for i in range(m):
        for j in range(n):
            if map_m[i][j] == 4 and d_m[i][j] >= b2:
                map_m[i][j] = 2
                t = 0
                
            elif map_m[i][j] == 5 and d_m[i][j] >= b1:
                map_m[i][j] = 3
                t = 0

    count += 1

    if t:
        break

for a in out_m:
    print(*a)

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_M = 100;
const int MAX_N = 100;

int M, N, a1, a2, b1, b2;
int Map[MAX_M][MAX_N];
int InfectionDay[MAX_M][MAX_N];
int danger[MAX_M][MAX_N];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

struct Position {
    int x, y, danger;
    bool operator<(const Position& other) const {
        return danger < other.danger;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> M >> N >> a1 >> a2 >> b1 >> b2;

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> Map[i][j];
        }
    }

    memset(InfectionDay, -1, sizeof(InfectionDay));

    int day = 0;
    bool hasNewInfection = true;

    while (hasNewInfection) {
        hasNewInfection = false;

        memset(danger, 0, sizeof(danger));

        priority_queue<Position> pq;

        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (Map[i][j] == 2 || Map[i][j] == 3) {
      
                    int initial_danger = (Map[i][j] == 2) ? a2 : a1;
                    danger[i][j] = initial_danger;
                    pq.push({i, j, initial_danger});
                }
            }
        }


        while (!pq.empty()) {
            Position current = pq.top();
            pq.pop();

            if (current.danger < danger[current.x][current.y]) {
                continue;
            }

            for (int dir = 0; dir < 4; ++dir) {
                int nx = current.x + dx[dir];
                int ny = current.y + dy[dir];

                if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
                if (Map[nx][ny] == 1) continue;

                int new_danger = current.danger - 1;
                if (new_danger <= 0) continue;

                if (new_danger > danger[nx][ny]) {
                    danger[nx][ny] = new_danger;
                    pq.push({nx, ny, new_danger});
                }
            }
        }

  
        vector<pair<int, int>> newlyInfected;

        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (Map[i][j] == 4 || Map[i][j] == 5) {
                  
                    int infection_threshold = (Map[i][j] == 4) ? b2 : b1;
                    if (danger[i][j] >= infection_threshold) {
                        InfectionDay[i][j] = day + 1;
                        newlyInfected.push_back({i, j});
                        hasNewInfection = true;
                    }
                }
            }
        }


        for (auto& pos : newlyInfected) {
            int i = pos.first;
            int j = pos.second;
            if (Map[i][j] == 4) {
                Map[i][j] = 2; 
            } else if (Map[i][j] == 5) {
                Map[i][j] = 3;
            }
        }

        day++;
    }


    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            if (Map[i][j] == 0 || Map[i][j] == 1) {
                cout << -1;
            } else if (InfectionDay[i][j] == -1) {
                if (Map[i][j] == 2 || Map[i][j] == 3) {
                    cout << 0;
                } else {
                    cout << -1;
                }
            } else {
                cout << InfectionDay[i][j];
            }
            if (j != N - 1) cout << " ";
        }
        cout << endl;
    }

    return 0;
}