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.

Example 1:

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

Example 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.

Example 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.

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;

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;
    }
}