When several things spread at the same speed from several starting points, put all of them in the BFS queue before you start. Every layer of the search is then one unit of time, no matter how many sources there are.
You are given an m x n grid where each cell is 0 (empty), 1 (fresh orange) or 2 (rotten orange). Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes until no cell has a fresh orange. If that is impossible, return -1.
Examples
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: the orange in the bottom-left corner is never reached
Input: grid = [[0,2]]
Output: 0
Explanation: there are no fresh oranges to begin with
Constraints
1 <= m, n <= 10- Target: O(m * n) time
Goals
- Seed a BFS queue with several sources at once so every source spreads simultaneously
- Process BFS level by level to count elapsed time
- Detect unreachable cells after the search finishes