# 994. Rotting-Oranges

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/02/16/oranges.png)

<pre><code>Input: [[2,1,1],[1,1,0],[0,1,1]]
<strong>Output: 
</strong>4
</code></pre>

**Example 2:**

<pre><code>Input: [[2,1,1],[0,1,1],[1,0,1]]
<strong>Output: 
</strong>-1
<strong>Explanation: 
</strong> The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
</code></pre>

**Example 3:**

<pre><code>Input: [[0,2]]
<strong>Output: 
</strong>0
<strong>Explanation: 
</strong> Since there are already no fresh oranges at minute 0, the answer is just 0.
</code></pre>

&#x20;

**Note:**

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

## Method One

```
class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        if( rows < 1 ) return 0;
        int columns = grid[0].length;
        
        Queue<int[]> bfsQueue = new LinkedList<>();
        int oranges = 0;
        
        for( int i = 0; i < rows; i++ ) {
            for( int j = 0; j < columns; j++ ) {
                if( grid[i][j] == 1 || grid[i][j] == 2) {
                    oranges += 1;
                }
                if( grid[i][j] != 2 ) {
                    continue;
                }
                bfsQueue.offer( new int[]{i,j} );
            }
        }
        
        if( bfsQueue.size() == 0 ) {
            return oranges == 0 ? 0 : -1;
        } 
        
        int time = -1;
        
        while( !bfsQueue.isEmpty() ) {
            int size = bfsQueue.size();
            while( size > 0 ) {
                size -= 1;
                oranges -= 1;
                int[] cur = bfsQueue.poll();
                int row = cur[0];
                int col = cur[1];
                if( row > 0 && grid[ row - 1 ][ col ] == 1 ) {
                    bfsQueue.offer( new int[]{ row - 1, col } );
                    grid[ row - 1 ][ col ] = 2;
                }
                if( row < rows - 1 && grid[ row + 1 ][ col ] == 1 ) {
                    bfsQueue.offer( new int[]{ row + 1, col });
                    grid[ row + 1 ][ col ] = 2;
                }
                if( col > 0 && grid[ row ][ col - 1 ] == 1 ) {
                    bfsQueue.offer( new int[]{ row, col - 1} );
                    grid[ row ][ col - 1 ] = 2;
                }
                if( col < columns - 1 && grid[ row ][ col + 1 ] == 1 ) {
                    bfsQueue.offer( new int[]{ row, col + 1 });
                    grid[ row ][ col + 1 ] = 2;
                }               
            }
            time += 1;
        }
        return oranges == 0 ? time : -1;
        
    }
}
​
```

Same idea, better code;

```java
class Solution {
    private int[] directions = {1, 0, -1, 0, 1};
    public int orangesRotting(int[][] grid) {
        //bfs
        int M = grid.length;
        int N = grid[0].length;
        int totalFresh = 0;
        ArrayDeque<int[]> queue = new ArrayDeque<>();
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                if(grid[i][j] == 1) totalFresh++;
                if(grid[i][j] == 0) continue;
                if(grid[i][j] == 2) queue.offer(new int[]{i, j});
            }
        }
        if(totalFresh == 0) return 0;
        int steps = -1;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                int[] cur = queue.poll();
                for(int i = 0; i < directions.length - 1; i++){
                    int nextRow = cur[0] + directions[i];
                    int nextCol = cur[1] + directions[i + 1];
                    if(nextRow < 0 || nextCol < 0 || nextRow >= M || nextCol >= N) continue;
                    if(grid[nextRow][nextCol] == 1) {
                        grid[nextRow][nextCol] = 2;
                        totalFresh--;
                        queue.offer(new int[]{nextRow, nextCol});
                    }
                }
                size--;
            }
            steps++;
        }
        return totalFresh == 0 ? steps : -1;
    }
}
```
