面试题6--腐烂的苹果（多源DFS）

腐烂的苹果（多源DFS）

文章目录

• 腐烂的苹果（多源DFS）
• • 解题思路
  • 代码拟写及相关注意点
  • 总结

题目链接： 腐烂的苹果_多源DFS

描述

给定一个 n × m 的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。

其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。

腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1

数据范围

1≤ n ,m ≤1000 ，网格中的值满足 0≤val≤2

解题思路

这个任务需要用广度优先搜索（BFS）来进行处理，并且由于我们需要在最短时间内扩散腐烂的苹果。我们可以把每一个被坏掉的苹果当作一个起点，并从这些起点同时展开扩散。

1. 初始化队列： 首先将所有初始状态标记为腐烂的苹果的位置信息存储于预定义的队列中，这些位置信息代表了