Initialize a BFS queue with all initially contaminated cells, then expand level by level.

Rotting Oranges

medium

Acceptance: 51%

GraphsBFS

A grid contains empty cells (0), fresh items (1), and contaminated items (2). Each minute, any fresh item adjacent (up/down/left/right) to a contaminated item becomes contaminated. Report the minimum number of minutes until every item is contaminated, or -1 if some items can never be reached.

Examples

Example 1:

Input:grid = [[1,2,1],[1,1,1],[0,1,2]]

Output:2

Explanation: Both contaminated cells spread outward; after 2 minutes all fresh items are reached.

Example 2:

Input:grid = [[2,1,0],[0,1,0],[0,0,1]]

Output:-1

Explanation: The item at (2,2) is isolated and cannot be contaminated.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Rotting Oranges

Examples

Hints

Related Problems