总结：网格扩散类问题 / 多源 BFS 问题

目录一、这类题的本质二、三道题的统一抽象1、腐烂的橘子2、矩阵扩散3、宜居星球改造计划三、该类型题目的解题套路第一步：明确状态含义第二步：遍历矩阵，初始化队列第三步：处理特殊情况1、没有待扩散目标2、没有扩散源，但存在待扩散目标第四步：使用 BFS 按层扩散第五步：四方向扩散第六步：判断边界和目标状态第七步：扩散并入队第八步：更新时间第九步：返回结果四、通用模板：多源 BFS 扩散模板五、针对三道题如何套模板1、腐烂的橘子2、矩阵扩散3、宜居星球改造计划六、更加具体的通用代码模板通用扩散模板用这个模板解决腐烂的橘子用这个模板解决宜居星球矩阵扩散稍微特殊七、什么场景使用这个模板？1、二维网格2、上下左右扩散或移动3、多个初始起点同时开始4、每一步代价相同5、要求最短时间 / 最少步数6、可能存在无法到达的区域八、典型题目关键词总结九、多源 BFS 与单源 BFS 的区别1、起点数量不同单源 BFS多源 BFS2、初始化方式不同单源 BFS 初始化多源 BFS 初始化3、含义不同单源 BFS多源 BFS4、是否需要统计 remain单源 BFS多源 BFS5、终止条件不同单源 BFS多源 BFS6、时间变量处理不同单源 BFS多源 BFS十、单源 BFS 通用模板十一、多源 BFS 通用模板十二、单源 BFS 和多源 BFS 对比总结十三、这类题的常见坑点1、没有把所有源点一次性入队2、时间多加一轮3、没有及时修改状态4、用 shift 出队导致性能差5、没有处理无源点情况十四、最终记忆口诀十五、总结一、这类题的本质这类题本质上是：多源 BFS 求最短扩散时间可以把二维矩阵看成一张图：每个格子是一个节点；上下左右相邻的格子之间有边；每条边的权重都是1；所有初始扩散点同时作为起点；BFS 每向外扩展一层，就代表时间增加1。