994. Rotting Oranges

 一刷 06/2022

Version #1 DFS

Time O(MN)

Space O(MN) - the worst case is that all grids have rotten oranges

Runtime: 2 ms, faster than 95.71% of Java online submissions for Rotting Oranges.

Memory Usage: 42.7 MB, less than 62.00% of Java online submissions for Rotting Oranges.

class Solution {

    private static int[] dx = new int[]{1, 0, -1, 0};

    private static int[] dy = new int[]{0, -1, 0, 1};

    private static int EMPTY = 0;

    private static int FRESH = 1;

    private static int ROTTEN = 2;

    public int orangesRotting(int[][] grid) {

        int rows = grid.length;

        int cols = grid[0].length;

        int freshCnt = 0;

        Queue<int[]> que = new ArrayDeque<>();

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (grid[y][x] == FRESH) {

                    freshCnt++;

                }

                if (grid[y][x] == ROTTEN) {

                    que.offer(new int[]{y, x});

                }

            }

        }

        if (freshCnt == 0) {

            return 0;

        }

        int mins = 0;

        while (!que.isEmpty()) {

            mins++;

            int size = que.size();

            while (size-- > 0) {

                int[] curr = que.poll();

                for (int i = 0; i < 4; i++) {

                    int y = curr[0] + dy[i];

                    int x = curr[1] + dx[i];

                    if (x < 0 || y < 0 || x >= cols || y >= rows || grid[y][x] != FRESH) {

                        continue;

                    }

                    grid[y][x] = ROTTEN;

                    freshCnt--;

                    if (freshCnt == 0) {

                        return mins;

                    }

                    que.offer(new int[]{y, x});

                }

                

            }

        }

        return -1;

    }

}