题目重点：同步按天传播 K 邻居阈值感染，每个新感染格只贡献一次给邻居计数。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 网格为矩形二值矩阵，八邻接含斜对角，不含自身；每天同时根据上一天状态决定新增感染。
- 返回发生新增感染的天数；初始状态为第 0 天，首次变化算第 1 天。K≥0，K=0 时所有尚健康格在第 1 天感染；若 K>8 无新增。
- 题目未明确出同步/异步更新的样例，本文按常见同步传播训练契约，需面试时确认。
解题路线
- 维护当天新感染 frontier；对每个 frontier 格，给仍健康的八邻居累计已感染邻居数。
- 当健康格累计数第一次达到 K，就加入下一天 frontier；当前整批 frontier 处理完才把下一批标成感染，保证同步。
- 每个格最多入 frontier 一次，每次最多检查八条邻接关系，故 O(MN)；K=0 用直接边界处理。
- 用每一天完整扫描棋盘并同步更新的独立慢实现，对所有 512 个 3×3 二值棋盘和 K=0..9 共 5,120 组对照。
手动走一遍
3×3 棋盘中心健康、其上下左右四格已有两格感染，K=2 时中心在第 1 天感染；中心成为第 1 天感染者，其邻居只能在第 2 天因中心而感染，不能在第 1 天连锁生效。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def days_until_stable(grid: list[list[int]], threshold: int) -> int:
"""Synchronous 8-neighbor threshold infection; return days with new cases."""
if threshold < 0:
raise ValueError("threshold must be non-negative")
if not grid or not grid[0]:
return 0
rows, cols = len(grid), len(grid[0])
if any(len(row) != cols or any(value not in (0, 1) for value in row) for row in grid):
raise ValueError("grid must be rectangular and binary")
current = [row[:] for row in grid]
if threshold == 0:
return 1 if any(0 in row for row in current) else 0
neighbors = [
(dr, dc)
for dr in (-1, 0, 1)
for dc in (-1, 0, 1)
if dr or dc
]
infected_frontier = [
(r, c)
for r in range(rows)
for c in range(cols)
if current[r][c] == 1
]
infected_neighbor_count = [[0] * cols for _ in range(rows)]
days = 0
while infected_frontier:
next_frontier = []
for row, col in infected_frontier:
for dr, dc in neighbors:
nr, nc = row + dr, col + dc
if 0 <= nr < rows and 0 <= nc < cols and current[nr][nc] == 0:
infected_neighbor_count[nr][nc] += 1
if infected_neighbor_count[nr][nc] == threshold:
next_frontier.append((nr, nc))
if not next_frontier:
break
for row, col in next_frontier:
current[row][col] = 1
days += 1
infected_frontier = next_frontier
return days
复杂度
时间 O(MN) 因每格被处理一次、每次最多八个邻居；计数、状态副本与 frontier 最坏 O(MN) 空间。若初始/潜在活跃格极稀疏，可用坐标哈希表只存活跃邻域，代价是邻居查找哈希开销。
易错点与追问
容易失分的边界
- 原地扫描时立即感染并影响同一天后续格，偷偷改成异步传播。
- 只算上下左右四邻居，漏掉对角。
- 重复全图扫描每一天，最坏 O(MN×天数)。
- 同一健康格被多个 frontier 邻居重复入队，导致错误天数与重复处理。
- K=0、无初始感染与 K>8 这些极端条件未定义。
继续深挖
- 如果邻居是四方向，代码和复杂度如何变？
- 若不同格的 K 不同，是否仍能用同一个计数 frontier？
- 若感染可恢复或有时效，单调计数为何不再正确？
- 超大稀疏无限棋盘如何只保存活动坐标？
