OpenAI 高频题详解：Infection Spread（感染扩散）
文章目录
LeetCode 994「腐烂的橘子」的豪华 5 连问版 · OpenAI 面经库 Very high 频率 · 最后一次被问到 2026-09-26 · phone screen / tech screen · 60 分钟
干净做完 Part 1–3 就能拿 strong；Part 5 极少有人走到，不用死磕。
Part 1：基础传播
M×N 网格，0 = 健康，1 = 感染。
-
每天，每个感染格同时感染上下左右 4 个邻居里的健康格（对角线不算）
-
当天新感染的格子，第二天才开始传播
-
允许多个感染源
-
返回全感染需要的天数；不可能则返回 -1（没有感染源，或有永远到不了的格子）
其实通用规则是：健康格在有 ≥N 个感染邻居时，下一天被感染。Part 1 是 N=1 的特例——后面会加码。
边界 case：空网格、无感染源（→ -1）、开局全感染（→ 0）、1×1、单行单列（一维传播）。
小例子：3×3 中心一个感染源 → 2 天（第 1 天染 4 个邻居，第 2 天染 4 个角）；单行 [1,0,0,0,0] → 4 天。
Part 2：免疫细胞
引入 2 = 免疫：永不被感染，也不传播，数邻居时直接跳过。
返回所有可达健康格被感染的天数；如果有健康格被免疫墙永久封死，返回 -1。
注意编码变体：有的版本用 -1 表示免疫，或用字母 . / X / I ——动手前先问清楚编码再写。
Part 3：D 天后自愈（最容易翻车的一问）
-
被感染 D 天后，格子自愈变免疫，不再传播
-
结束条件：没有活跃感染格（网格稳定；允许有永远健康的格子存在）
最大坑：off-by-one + 顺序。第 t 天感染的格子，当 current_day - t >= D 时变免疫（注意是 >= 不是 >），并且免疫先生效、再传播——同一 tick 内，先算谁痊愈，再用剩下的格子传播。顺序反了，答案就错。
Part 4：阈值 + 死亡（三个变体，先问清是哪一个）
-
变体 A：健康格需要 ≥K 个感染邻居才会被感染（阈值传播，N 从 1 变成 K）
-
变体 B：感染格周围若有 ≥K 个感染邻居，开始死亡倒计时，N 天后死亡；严格版里，顶着 ≥K 个感染邻居被感染的格子，康复计时到时直接死亡而不是变免疫。返回总天数 + 死亡总数。
-
变体 C：Part 1+2+3+死亡全叠加
动手前必须问：K 到底是感染阈值、死亡阈值，还是两个都是？
Part 5：每天烧一行/一列
每天选任意一行或一列烧掉，最小化总死亡数。变体：也可以选择不烧。先问清是单次决策还是每天重复决策。
说实话，能走到这里的人很少。有些面试官会把这部分换成工程 follow-up："网格很大怎么办"。
解法总览
Parts骨架复杂度1–2多源 BFSO(R·C) 时间 + 空间3–4同步更新模拟（double buffer）O((R·C)²) 时间5优化问题，讲建模思路即可—
Part 1–2：多源 BFS，教科书级
所有初始感染格同时入队（第 0 层），一层一层向外扩 4 邻居，数层数。每个格子最多入队出队一次。
"当天新感染第二天才传播"正好对应 BFS 的层边界——按层遍历，天然满足。不要写成 DFS，也不要手滑写成 8 邻居。
Part 2 几乎零改动：遇到 2 直接跳过；最后检查还有没有健康格残留（被墙死的），有就返回 -1。
Part 3–4：同步更新，double buffer
一旦格子带了"状态"（已感染天数、死亡倒计时、阈值判定），纯 BFS 骨架就不够用了。标准打法：
-
快照当前网格
-
基于快照算每个格子的下一状态
-
整体替换
头号 bug 来源：在同一天内 in-place 直接改。改完的格子会影响同一天还没算的邻居，传播会"加速"，天数算小。
Part 3 的常用实现：维护 infect_day[i][j]（每个格子的感染日期），或 day → 格子集合 的 hashmap（哪天有哪些格子痊愈）。每个 tick 两步走：
-
先算谁变免疫：current_day - infect_day >= D，从活跃集合移除
-
再用剩下的活跃格子做传播（只从本 tick 开始时的快照传播）
一个值得主动说的复杂度对比
Part 1 有两种写法，面试官可能会追问：
-
多源 BFS：每个格子只碰一次，O(R·C)
-
朴素逐天模拟：每天全网格扫一遍找"邻居够数"的格子，最多扫 R·C 天 → O((R·C)²)
模拟更容易扩展到 Part 3/4（状态一多，BFS 就不好使了）。所以通常打法是 Part 1–2 用 BFS，Part 3 起切模拟——主动说出这个 trade-off 很加分。
参考代码（Python）
Part 1
from collections import deque
def time_to_full_infection(grid):
if not grid or not grid[0]:
return -1
R, C = len(grid), len(grid[0])
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque()
healthy = 0
for i in range(R):
for j in range(C):
if grid[i][j] == 1:
q.append((i, j)) # 多源：全部入队，第 0 层
elif grid[i][j] == 0:
healthy += 1
if healthy == 0:
return 0 # 开局全感染
if not q:
return -1 # 没有感染源
days = 0
while q and healthy > 0:
days += 1
for _ in range(len(q)): # 按层遍历 = "当天新感染明天再传"
i, j = q.popleft()
for di, dj in DIRS:
ni, nj = i + di, j + dj
if 0 <= ni < R and 0 <= nj < C and grid[ni][nj] == 0:
grid[ni][nj] = 1
healthy -= 1
q.append((ni, nj))
return days if healthy == 0 else -1
Part 2（免疫格）：在上面基础上，2 直接跳过，healthy 只数非免疫格；结尾同样检查残留。
Part 3（D 天自愈）
def time_to_stable_state(grid, D):
if not grid or not grid[0]:
return 0
R, C = len(grid), len(grid[0])
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = float('inf')
infect_day = [[INF] * C for _ in range(R)]
active = set()
for i in range(R):
for j in range(C):
if grid[i][j] == 1:
infect_day[i][j] = 0
active.add((i, j))
day = 0
while active:
day += 1
# 第 1 步：先算谁变免疫（免疫先生效，注意 >=）
healed = {(i, j) for (i, j) in active
if day - infect_day[i][j] >= D}
active -= healed
# 第 2 步：用剩下的活跃格子传播（快照：只从本 tick 开始时的集合传）
spreaders = list(active)
for i, j in spreaders:
for di, dj in DIRS:
ni, nj = i + di, j + dj
if 0 <= ni < R and 0 <= nj < C and infect_day[ni][nj] == INF:
infect_day[ni][nj] = day
active.add((ni, nj))
return day
备考清单
-
Part 1–3 在 30–40 分钟内写完且测试通过，是"strong"的线
-
必练：同步更新（double buffer）、off-by-one、多源 BFS、免疫墙
-
别炫技：清晰 > 巧妙，用最简单的实现
-
8 邻居变体、编码变体（-1 / 字母）、停止条件变体——动手前先问清
