OpenAI 面试真题解析：感染植物传播模拟、免疫更新与 K 天治愈规则

An infected plant spreads infection to neighboring plants. If a plant is surrounded by D infected plants, it also becomes infected. How many days until all plants are infected?

Follow-up: some plants can become infection-proof after the infection changes. What update is needed?

Follow-up: after K days, an infected plant can be healed and become infection-proof. What update is needed?

这道题本质上是一个网格 / 图上的感染扩散模拟问题：初始时部分植物为感染状态，感染会随着“相邻传播”逐日扩散，当某个植物周围有达到阈值 D 的感染邻居时也会被感染。通常可以用 BFS 多源扩散来按天推进，记录每个位置第一次被感染的时间，从而计算全局感染完成所需天数。两个 follow-up 则把状态机进一步复杂化：一类植物感染后会变成免疫状态，另一类植物在 K 天后可被治愈并转为免疫，因此需要在队列 / 事件驱动模拟中维护多种状态，并在更新时同步处理“感染、免疫、治愈”之间的转换。