Rotting Oranges

1package pkg5leetcode.interview150;2 3/*4 * Rotting Oranges | LC 9945 * APPROACH: Multi-source BFS from rotten oranges; count minutes.6 * COMPLEXITY: Time O(m*n), Space O(m*n)7 */8import java.util.*;9 10public class interview150_LC994RottingOranges {11    static int orangesRotting(int[][] grid) {12        int m = grid.length, n = grid[0].length, fresh = 0;13        Deque<int[]> q = new ArrayDeque<>();14        for (int r = 0; r < m; r++) {15            for (int c = 0; c < n; c++) {16                if (grid[r][c] == 2) q.add(new int[]{r, c});17                else if (grid[r][c] == 1) fresh++;18            }19        }20        int mins = 0;21        while (!q.isEmpty() && fresh > 0) {22            int size = q.size();23            for (int s = 0; s < size; s++) {24                int[] p = q.poll();25                for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {26                    int nr = p[0] + d[0], nc = p[1] + d[1];27                    if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] == 1) {28                        grid[nr][nc] = 2;29                        fresh--;30                        q.add(new int[]{nr, nc});31                    }32                }33            }34            mins++;35        }36        return fresh == 0 ? mins : -1;37    }38 39    public static void main(String[] args) {40        check(orangesRotting(new int[][]{{2,1,1},{1,1,0},{0,1,1}}) == 4, "case1");41        check(orangesRotting(new int[][]{{2,1,1},{0,1,1},{1,0,1}}) == -1, "case2");42        System.out.println("all tests passed");43    }44 45    static void check(boolean cond, String name) {46        if (!cond) throw new AssertionError("FAILED: " + name);47        System.out.println("  PASS " + name);48    }49}