Rotting Oranges

1package pkg5leetcode.official75;2 3/*4 * Rotting Oranges | LC 9945 * APPROACH: Multi-source BFS spread rot minute by minute.6 * COMPLEXITY: Time O(mn), Space O(mn)7 */8import java.util.*;9 10public class official75_LC994RottingOranges {11    static int orangesRotting(int[][] grid) {12        int m = grid.length, n = grid[0].length, fresh = 0, minutes = 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        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};19        while (!q.isEmpty() && fresh > 0) {20            minutes++;21            int size = q.size();22            for (int i = 0; i < size; i++) {23                int[] cur = q.poll();24                for (int[] d : dirs) {25                    int r = cur[0] + d[0], c = cur[1] + d[1];26                    if (r >= 0 && c >= 0 && r < m && c < n && grid[r][c] == 1) {27                        grid[r][c] = 2;28                        fresh--;29                        q.add(new int[]{r, c});30                    }31                }32            }33        }34        return fresh == 0 ? minutes : -1;35    }36 37    public static void main(String[] args) {38        check(orangesRotting(new int[][]{{2,1,1},{1,1,0},{0,1,1}}) == 4, "case1");39        check(orangesRotting(new int[][]{{2,1,1},{0,1,1},{1,0,1}}) == -1, "case2");40        check(orangesRotting(new int[][]{{0,2}}) == 0, "case3");41        System.out.println("all tests passed");42    }43 44    static void check(boolean cond, String name) {45        if (!cond) throw new AssertionError("FAILED: " + name);46        System.out.println("  PASS " + name);47    }48}