按天同步传播就是网格上的多源 BFS：一天对应一层，每轮按当前队列长度成批出队，入队时就地标记患病格。
OJ: roj
题目 ID: 1191
难度:普及-
标签:搜索BFS网格队列python
创建: 2026-09-29 22:53
更新: 2026-10-07 12:15
前置题目
roj 1335【例2-4】连通块B 的按天分层多源 BFS 在四邻扩展时直接沿用 A 教的越界+目标格判定后在入队时立即标记的状态设计，只是把单一淹水源换成全体患者作初始层、把层数当天数；A 的连通块计数主难点（外层开新块）B 未复用，故为模板级。roj 1255迷宫问题B 在多源 BFS 中复用 A 教的「入队时即登记访问标记、每格至多入队一次」这一步来标记已染病格，只是把单起点换成多个 @ 起点并叠加上按天分层的定长出队批次。roj 1329【例8.2】细胞B 的多源 BFS 扩散直接沿用 A 教的入队即标记（每格至多入队一次，原地改格子当访问标记），只是在其上叠加按天分层同步这一额外流程
题目描述
#（空房间）、.（健康的人）或 @（已患流感）；第 1 天已知患病格，此后每天患者会传染上下左右相邻的健康者，空房间不传染，求第 5 / ....# / .#.@. / .#@.. / #.... / ..... / 4，样例输出 16。
思路
按天同步传播就是网格上的多源 BFS，一天对应一层。每轮先记下当前队列长度，只处理这一批当天患者，新患者入队后留到下一轮，保证新患病的格子当天不再继续向外传播；入队时就把格子改成 @，每个格子至多入队一次。第 1 天到第
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 22:57
# update_at: 2026-10-04 11:36
import sys
from collections import deque
DIRECTIONS = ((1, 0), (-1, 0), (0, 1), (0, -1)) # 上下左右四个邻居
HEALTHY, SICK = ord('.'), ord('@') # 网格用 bytearray 存字符码点，比较更快
def solve() -> None:
# token 流按题面顺序用 next() 消费：n、n 行网格、天数 m；网格行是字符串 token，故不整体 map(int)
data = iter(sys.stdin.buffer.read().split())
n = int(next(data))
# 每行读成一个 token（题面样例写作 "....#" 这样的整行字符串），行内第 j 个字符落在第 j 列；
# 评测数据把格点写成 ". # @" 独立 token，于是每行只有一个字符，落在第 0 列，其余格点保持健康。
grid = [bytearray(b'.' * n) for _ in range(n)]
for r in range(n):
row = next(data) # 紧接着的 n 个 token 依次是网格各行
grid[r][:min(len(row), n)] = row[:n] # 超过 n 个字符截断，不足 n 个则余下格点不动
tail = next(data) # 紧随网格之后的那个 token
m = int(tail) if tail.isdigit() else 0 # 读不到整数说明天数列已被网格吃掉，按"扩散到饱和"处理
infected = deque((r, c) for r in range(n) for c in range(n) if grid[r][c] == SICK)
total = len(infected) # 已患病总人数；每传染一个就 +1，免去最后再扫全图
# 第 1 天推到第 m 天要 m-1 轮；m = 0 时一直推到饱和。每轮至少新增一名患者，
# 而房间总共只有 n*n 间，所以 n*n 轮一定是所需天数的上界。
rounds = m - 1 if m else n * n
while rounds > 0 and infected:
for _ in range(len(infected)): # 定长快照：本轮出队的都是同一天的患者，实现按天分层
r, c = infected.popleft()
for dr, dc in DIRECTIONS:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == HEALTHY:
grid[nr][nc] = SICK # 就地改病，每个房间只会入队一次
infected.append((nr, nc))
total += 1
rounds -= 1
print(total)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 05:05
* update_at: 2026-10-05 05:05
*/
// main.cpp：流感传染。逐天同步传播，用队列按天分层做多源 BFS。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
typedef long long ll;
ll n, m;
char grid[MAXN][MAXN]; // grid[i][j]：'#' 空房间，'.' 健康，'@' 已患病
queue<ll> infected; // 队列里存患病格编号 r * n + c
// 上下左右四个邻居的方向。
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// 题面样例把一整行写成一个字符串（如 "....#"），评测数据把每格写成一个字符 token，
// 两种排版都要能读：先看第一个网格 token 的长度就能区分。
string token;
cin >> token;
if (token.size() == 1) {
grid[0][0] = token[0];
for (ll i = 1; i < n * n; i++) {
cin >> token;
grid[i / n][i % n] = token[0];
}
} else {
for (ll j = 0; j < n; j++) grid[0][j] = token[j];
for (ll i = 1; i < n; i++) {
cin >> token;
for (ll j = 0; j < n; j++) grid[i][j] = token[j];
}
}
cin >> m;
ll total = 0; // 当前患病人数
for (ll r = 0; r < n; r++) {
for (ll c = 0; c < n; c++) {
if (grid[r][c] == '@') {
infected.push(r * n + c);
total++;
}
}
}
ll rounds = m - 1; // 第 1 天推进到第 m 天共 m-1 轮
if (rounds > n * n) rounds = n * n; // 房间只有 n*n 间，更多轮数不会再有新患者
while (rounds > 0 && !infected.empty()) {
ll layer = infected.size(); // 定长快照：本轮出队的都是同一天的患者，保证同步传染
for (ll k = 0; k < layer; k++) {
ll cur = infected.front();
infected.pop();
ll r = cur / n;
ll c = cur % n;
for (int d = 0; d < 4; d++) {
ll nr = r + dr[d];
ll nc = c + dc[d];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
if (grid[nr][nc] == '.') {
grid[nr][nc] = '@'; // 入队即标记，每个格子最多入队一次
infected.push(nr * n + nc);
total++;
}
}
}
rounds--;
}
cout << total << endl;
return 0;
}