这道 OpenAI 面试题看起来像一个很简单的 grid simulation：有些植物一开始已经感染，感染植物每天会影响相邻植物；如果某个健康植物周围感染植物数量达到 D，它也会被感染。问题是：多少天以后所有植物都会被感染？
英文原题大意如下：
Infected plant spread infection to neighbors, if a plant is surrounded by D infected plant it also get infected, how many days until all infected?
Follow up 1: some plants are infection proof, what update?
Follow up 2: say after K days an infected plant can be healed and become infection proof, what update?
题目没有把所有输入格式写死，所以面试时第一步很重要：先把模型问清楚。一般可以假设有一个 m x n 的二维矩阵，每个 cell 代表一株植物。状态可能包括：
健康植物：还没有感染。
感染植物：可以影响周围植物。
免疫植物：永远不会被感染，也不会传播感染。
这里的 neighbors 通常需要确认是四方向还是八方向。如果面试官没有特别说明，先按四方向上下左右处理；如果他说包括 diagonal，再扩展成八方向即可。
这题的核心不是单纯 BFS，因为它多了一个条件：一个植物不是被任意一个感染邻居感染，而是要周围感染邻居数量达到 D 才感染。
所以我们需要维护每个健康植物当前受到多少个感染邻居影响。
中文题目版本
给定一个二维花园网格，其中有些植物一开始已经感染。每天，感染植物会向周围相邻植物传播感染。对于任意一株健康植物，如果它周围已经感染的植物数量达到 D，那么它会在当天结束时变成感染状态。
请问最少需要多少天，才能让所有可以被感染的植物都变成感染状态？
Follow-up 1：如果有些植物是免疫植物，永远不会被感染，算法需要怎么改？
Follow-up 2：如果一株植物感染 K 天以后会自动康复，并且康复后变成免疫植物，算法需要怎么改？
面试中的解题思路
候选人可以先把题目理解成一个按天推进的过程。第 0 天有一批 infected plants。第 1 天，所有健康植物同时检查自己周围有多少感染植物；数量达到 D 的植物，会在第 1 天结束时感染。第 2 天继续用新的感染集合向外扩散。
这里容易出错的点是“同时发生”。不能一边遍历 grid，一边马上把植物改成 infected，再让它继续影响同一天后面的植物。这样会把一天内的传播链拉长，导致答案偏小。
比较稳的做法是用 BFS 的层级思想：
先把所有初始感染植物放进 queue，它们的感染时间是 0。
然后为每个健康植物维护一个 infectedNeighborCount。
每当一个植物在某一天感染成功，它会在下一轮影响周围邻居。
邻居的计数加一。
如果某个健康邻居的计数达到 D，就把它加入 queue，并记录它的感染日期。
这样每个植物最多进入 queue 一次，每条边最多被处理常数次，所以复杂度很干净。
为什么不能直接普通 BFS？
普通 BFS 的逻辑是：只要一个感染植物碰到一个健康植物，健康植物就感染。
这题不一样。它要求某个健康植物周围至少有 D 个感染邻居。比如 D = 2，一个健康植物只接触到一个感染源时，不能马上感染；只有第二个感染邻居出现时，它才会进入感染队列。
所以这里的 queue 不是用来表示“接触到了就感染”，而是表示“已经满足感染条件，可以从某一天开始继续传播”。
示例理解
假设 D = 2，某个健康植物旁边第一天只有一个感染邻居，它的计数变成 1，还不能感染。后来另一个相邻植物也感染了，它的计数变成 2，这时它才会被安排在对应日期感染。
这也是题目的关键：感染传播依赖多个邻居的累计影响，而不是单一来源。
返回值怎么定义？
面试中可以主动确认：
如果所有植物最终都能感染，返回最后一个植物感染的天数。
如果存在植物永远无法感染，返回 -1。
如果一开始所有非免疫植物都已经感染，返回 0。
这个返回值定义很重要，尤其是 follow-up 里有 infection-proof plants 时，有些植物本来就不应该算进“需要感染”的目标里。
Follow-up 1：Some plants are infection-proof
如果有些植物是 infection-proof，它们永远不会被感染。这个改动不大，主要有两点：
第一，免疫植物不加入待感染目标。也就是说，最后判断是否 all infected 时，只看普通植物，不看 infection-proof plants。
第二，传播时跳过免疫植物。感染植物影响邻居时，如果邻居是 immune/proof，直接忽略，不增加它的 infected neighbor count。
整体框架仍然是 BFS + neighbor count。只是状态多了一类：
healthyinfectedimmune
最后统计感染数量时，只需要确认所有可感染植物都已经感染。如果还有 healthy plant 的计数永远达不到 D，queue 会提前空掉，这时返回 -1。
Follow-up 2：After K days an infected plant can be healed and become infection-proof
这个 follow-up 比第一问难很多，因为感染状态不再永久存在。
原题说：一株植物感染 K 天之后会被治愈，并且变成 infection-proof。这里需要先问面试官一个关键问题：
一株植物感染期间是否每天都算作 infected neighbor？
通常合理理解是：感染后的第 t 天到第 t + K - 1 天，它都能作为感染邻居；到第 t + K 天，它康复并变成 immune，之后不再传播，也不再被感染。
这时原来的 BFS 不够了，因为一个邻居的 infected count 可能增加，也可能减少。之前永久感染时，计数只会单调增加；现在感染会过期，计数会下降。
更稳的做法是事件模拟：
当某个植物在 day t 感染时，对它的健康邻居贡献 +1。
同时安排一个 heal event，在 day t + K 发生。
当 heal event 到来时，这个植物变成 immune，并对周围健康邻居贡献 -1。
如果某个健康植物在某一天的 infected neighbor count 达到 D，它会在当天结束或下一天感染，这个时间规则需要和面试官确认。
这里最重要的变化是：infectedNeighborCount 不再只增不减，所以不能只靠普通 queue。需要按天处理 infect events 和 heal events。
Follow-up 2 的实现方式
可以维护两个按 day 分组的结构：
newInfections[day]：这一天新感染的植物。healEvents[day]：这一天需要康复的植物。
每天处理时，大致流程是：
先处理当天仍然有效的感染传播。
把达到 D 的健康植物收集起来，作为当天或下一天的新感染。
再处理到期康复，让对应植物变成 immune。
更新周围健康植物的 infected neighbor count。
这里的顺序需要和面试官确认，因为不同定义会影响边界答案。例如感染刚满 K 天的植物，在第 K 天是否还能传播一次？这类题面没写清楚的地方，不要自己硬猜，面试里主动问清楚反而是加分点。
如果希望实现更简单，也可以每天扫描全图，重新计算每个健康植物周围当前感染数量，然后决定下一天谁感染。这种做法更直观，复杂度是 O(days * m * n * neighbors)，在 grid 不大时可以接受。面试官追问优化时，再切到 event-based simulation。
时间复杂度
基础版和 Follow-up 1 中，每个 cell 最多感染一次，每次只检查固定数量邻居，所以时间复杂度是：
O(m * n)
空间复杂度也是：
O(m * n)
Follow-up 2 如果使用事件模拟，每个植物最多经历一次感染和一次康复，每次事件只影响固定数量邻居，理想情况下仍然可以做到：
O(m * n)
如果使用按天全图扫描，则复杂度会变成：
O(T * m * n)
其中 T 是模拟的天数。
这题面试时怎么讲更自然？
可以这样和面试官沟通：
我会把这个问题建模成一个 grid 上的 multi-source BFS。所有初始 infected plants 都是 day 0 的源点。不过和普通 BFS 不同，一个 healthy plant 不是第一次接触 infected neighbor 就感染，而是要累计 infected neighbor 数量达到 D。所以我会为每个 cell 维护一个 counter，表示它当前周围有多少 infected neighbors。每当一个 plant 被感染，它会更新周围健康植物的 counter；如果 counter 达到 D，这个健康植物就会被加入 queue，并记录感染日期。最后，如果所有可感染植物都被感染，返回最大感染日期；否则返回 -1。
Follow-up 里，如果有 infection-proof plants，我会把它们从目标集合里排除，并且传播时直接跳过。
如果 infected plants 在 K 天后会 healed 并变成 infection-proof，counter 就不再是单调增加的了。我会改成 event simulation，感染时给邻居贡献 +1，康复时把贡献撤掉 -1，并按 day 处理 infect/heal events。
csoahelp 做的就是这种场景里的实时辅助，题目刚读完就能给出完整思路，现场不用卡壳。
我们也有代面试，面试辅助，OA代写等服务助您早日上岸~
