腐烂的橘子

腐烂的橘子

class Solution {
    public int orangesRotting(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        
        int freshCount = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        //统计新鲜橘子数量，将腐烂橘子加入队列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    freshCount++;
                } else if (grid[i][j] == 2) {
                    queue.offer(i * n + j);
                }
            }
        }
        //全是新鲜的，直接返回
        if (freshCount == 0) return 0;
        //统计腐烂时间
        int minutes = 0;
        // BFS遍历
        while (!queue.isEmpty() && freshCount > 0) {
            minutes++;
            //每次都把那一分钟涉及的橘子处理了
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int index = queue.poll();
                int x = index / n;
                int y = index % n;
                // 上方向
                if (x - 1 >= 0 && grid[x - 1][y] == 1) {
                    grid[x - 1][y] = 2;
                    freshCount--;
                    queue.offer((x - 1) * n + y);
                }
                // 下方向
                if (x + 1 < m && grid[x + 1][y] == 1) {
                    grid[x + 1][y] = 2;
                    freshCount--;
                    queue.offer((x + 1) * n + y);
                }
                // 左方向
                if (y - 1 >= 0 && grid[x][y - 1] == 1) {
                    grid[x][y - 1] = 2;
                    freshCount--;
                    queue.offer(x * n + (y - 1));
                }
                // 右方向
                if (y + 1 < n && grid[x][y + 1] == 1) {
                    grid[x][y + 1] = 2;
                    freshCount--;
                    queue.offer(x * n + (y + 1));
                }
            }
        }
        //对比是否还存在新鲜橘子
        return freshCount == 0 ? minutes : -1;
    }
}