腐烂的橘子

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] 仅为 0、1 或 2

第一步：

• 计算所有新鲜的橘子的数量
• 将所有腐烂的橘子入队

第二步：

• 出队进行BFS
• 如果是新鲜的橘子则进行感染，直到新鲜的橘子数量为0，返回最短时间

class Solution {
    int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    boolean[][] visited;

    public int orangesRotting(int[][] grid) {
        int fresh = 0;
        visited = new boolean[grid.length][grid[0].length];
        Deque<int[]> que = new ArrayDeque<>();
        int time = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                } else if (grid[i][j] == 2) {
                    que.offer(new int[] { i, j });
                }
            }
        }
        if (fresh == 0) return 0;
        //bfs
        while (!que.isEmpty()) {
            int size = que.size();
            for (int k = 0; k < size; k++) {
                int[] cur = que.poll();
                int x = cur[0];
                int y = cur[1];
                visited[x][y] = true;
                if (grid[x][y] == 1) {
                    grid[x][y] = 2;
                    fresh--;
                    if (fresh == 0) {
                        return time;
                    }
                }
                for (int[] dir : dirs) {
                    int nX = x + dir[0];
                    int nY = y + dir[1];
                    if (nX >= 0 && nY >= 0 && nX < grid.length && nY < grid[0].length && !visited[nX][nY]
                            && grid[nX][nY] == 1) {
                        que.add(new int[] { nX, nY });
                    }
                }
            }
            time++;
        }
        return -1;
    }
}