题解 | 腐烂的苹果

使用一个队列记录腐烂的苹果的位置....

有点类似于二叉树的层序遍历....

import java.util.*;

public class Solution {
    public int rotApple(ArrayList<ArrayList<Integer>> grid) {
        int n = grid.size();
        int m = grid.get(0).size();

        //使用队列来进行广度优先搜索 (BFS)
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0; // 记录新鲜苹果的数量

        //将腐烂的苹果位置入队，并统计新鲜苹果的数量
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid.get(i).get(j) == 2) {
                    queue.offer(new int[] {i, j});
                } else if (grid.get(i).get(j) == 1) {
                    freshCount++;
                }
            }
        }

        if (freshCount == 0) return 0; //如果没有新鲜苹果，直接返回0

        //四个方向，分别是上、下、左、右
        int[] directions = {-1, 0, 1, 0, -1};
        int steps = 0;

        //BFS 开始腐烂
        while (!queue.isEmpty() && freshCount > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int x = current[0], y = current[1];

                //检查四个方向
                for (int d = 0; d < 4; d++) {
                    int nx = x + directions[d];
                    int ny = y + directions[d + 1];

                    //确保位置在有效范围内
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m && grid.get(nx).get(ny) == 1) {
                        grid.get(nx).set(ny, 2); //腐烂该位置
                        freshCount--; //新鲜苹果数减1
                        queue.offer(new int[] {nx, ny}); //将新腐烂的苹果入队
                    }
                }
            }
            steps++; //完成一轮腐烂，增加步骤数
        }

        return freshCount == 0 ? steps :
               -1; //如果所有新鲜苹果都腐烂了，返回步骤数，否则返回-1
    }
}