Rotting Oranges

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

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.
Solution:

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        if (n == 0) return 0;
        int[][] time = new int[m][n];
        for (int i = 0; i < m; i ++) {
            Arrays.fill(time[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (grid[i][j] == 2) {
                    bfs(grid, time, i, j);
                }
            }
        }
        int min = Integer.MIN_VALUE;
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (grid[i][j] == 1) {
                    if (time[i][j] == Integer.MAX_VALUE) {
                        return -1;
                    }
                    min = Math.max(min, time[i][j]);
                }
            }
        }
        return min == Integer.MIN_VALUE ? 0 : min;
    }
    
    private void bfs(int[][] grid, int[][] time, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        Deque<Integer> queue = new ArrayDeque<>();
        int[] dx = new int[]{-1,0,1,0};
        int[] dy = new int[]{0,1,0,-1};
        boolean[][] visited = new boolean[m][n];
        queue.offer(x * n + y);
        int t = 0;
        visited[x][y] = true;
        while (!queue.isEmpty()) {
            t ++;
            int size = queue.size();
            for (int s = 0; s < size; s ++) {
                int curr = queue.poll();
                int i = curr / n;
                int j = curr % n;
                for (int k = 0; k < 4; k ++) {
                    int ni = i + dx[k];
                    int nj = j + dy[k];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj] && grid[ni][nj] == 1) {
                        queue.offer(ni * n + nj);
                        visited[ni][nj] = true;
                        time[ni][nj] = Math.min(time[ni][nj], t);
                    }
                }
            }
        }
    }
}