995. Rotting Oranges — Multi-Source BFS

Given a grid where each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange), each minute any fresh orange adjacent (4-directionally) to a rotten one becomes rotten. Return the number of minutes until no fresh orange remains, or -1 if some fresh orange can never rot. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — minutes elapsed, or -1.

Examples

Input: {"grid":[[2,1,1],[1,1,0],[0,1,1]]}
Output: 4
Explanation: All rot in 4 minutes.

Input: {"grid":[[2,1,1],[0,1,1],[1,0,1]]}
Output: -1
Explanation: A fresh orange is unreachable.

Input: {"grid":[[0,2]]}
Output: 0
Explanation: No fresh oranges.

Constraints

• 1<=rows,cols<=100

Asked by