607. Rotting Oranges — BFS via Queue

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

Input: JSON {grid}.

Output: Integer — the minutes needed, or -1.

Examples

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

Input: {"grid":[[2,1,1],[0,1,1],[1,0,1]]}
Output: -1
Explanation: The bottom-left orange never rots.

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

Constraints

• 1<=rows,cols<=100

Asked by