[LeetCode] Problem 994 - Rotting Oranges

Posted on | In ,

In a given grid, each cell can have one of three values:

  • the value 0 representing an empty cell;
  • the value 1 representing a fresh orange;
  • the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example

No.1

uczODs.png

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

Output: 4

No.2

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

Output: -1

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

No.3

Input: [[0,2]]

Output: 0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Note

  1. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. grid[i][j] is only 0, 1, or 2.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public int orangesRotting(int[][] grid) {
    int result = 0;
    int m = grid.length;
    int n = grid[0].length;
    Queue<int[]> queue = new LinkedList<>();
    int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int count = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2)
                queue.offer(new int[] {i, j});
            else if (grid[i][j] == 1)
                count++;
        }
    }

    while (!queue.isEmpty() && count > 0) {
        int size = queue.size();
        result++;

        for (int i = 0; i < size; i++) {
            int[] pos = queue.poll();

            for (int[] dir : dirs) {
                int x = pos[0] + dir[0];
                int y = pos[1] + dir[1];

                if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1)
                    continue;
                
                queue.offer(new int[] {x, y});
                grid[x][y] = 2;
                count--;
            }
        }
    }

    return count == 0 ? result : -1;
}