腐烂的苹果

//每一个腐烂苹果，过了一分钟，都会影响上下左右（即下一个层次）苹果的状态，依次类推直到下一层次没有好苹果可以影响到（没有好苹果了，或者影响不到），明显的广度优先搜索
public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        //对应上下左右坐标的改变
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int m = grid.size(), n = grid.get(0).size();
        Queue<int[]> que = new LinkedList<>();
        int count = 0;
        //遍历，腐烂苹果的坐标放入队列，用于改变上下左右坐标处苹果的状态，count记录好苹果的数量，
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 2) {
                    que.add(new int[] {i, j});
                } else if (grid.get(i).get(j) == 1) {
                    count++;
                }
            }
        }
        int round = 0;
        while (count > 0 && !que.isEmpty()) {
            //过去了多少分钟
            round++;
            //队列长度会变，直接把que.size()放入for循环会出错
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] org = que.poll();
                //改变当前腐烂苹果的上下左右处苹果的状态
                for (int j = 0; j < 4; j++) {
                    int x = org[0] + dx[j];
                    int y = org[1] + dy[j];
                    //边界判定
                    if (x >= 0 && y >= 0 && x < m && y < n && grid.get(x).get(y) == 1) {
                        grid.get(x).set(y,2);
                        que.add(new int[] {x, y});
                        count--;
                    }
                }
            }
        }
        if (count != 0) {
            return -1;
        } else {
            return round;
        }

import java.util.*;


public class Solution {
    private static int[][] dirs = new int[][] {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };
    
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {  
        int n = grid.size(), m = grid.get(0).size();
        // que: 存放当前时刻已经腐烂的苹果
        Deque<int[]> que = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++){
                if (grid.get(i).get(j) == 2) {
                    que.add(new int[]{i, j});
                }
            }
        }
        int ans = 0;
        while(!que.isEmpty()) {
            ans++;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                int[] cur = que.pollFirst();
                int x = cur[0], y = cur[1];
                for (int[] dir : dirs) {
                    int x0 = x + dir[0];
                    int y0 = y + dir[1];
                    if (x0 >= 0 && x0 < n && y0 >= 0 && y0 < m 
                        && grid.get(x0).get(y0) == 1) {
                        grid.get(x0).set(y0, 2);
                        que.add(new int[]{x0, y0});
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid.get(i).get(j) == 1) {
                    return -1;
                }
            } 
        }
        // 除去初始时刻
        return ans - 1;
    }
}

/**
2 1 1
1 0 1
1 1 1
**/