/**
1. 先统计下新鲜的橘子有多少
2. 记录每次由新鲜变腐烂的橘子, 并由他们扩展开, 循环直到新鲜的橘子为0, 循环的次数为所求
3. 如果某次没有新鲜的橘子转化为腐烂的, 并且新鲜的橘子没完全消失, 返回-1
*/

class Solution {
    class Node{
        int x,y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    final int[] dx = {0, 0, 1, -1};
    final int[] dy = {1, -1, 0, 0};

    public int orangesRotting(int[][] grid) {
        int empty = 0, fresh = 0, rotten = 0;
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        ArrayList<Node>[] last = new ArrayList[2];
        last[0] = new ArrayList<Node>();
        last[1] = new ArrayList<Node>();
        int cur = 0;

        int n = grid.length, m = grid[0].length;
        for (int i = 0 ;i < n ; i ++){
            for (int j = 0; j < m ; j++){
                if (grid[i][j] == 1){
                    fresh ++;
                } else if (grid[i][j] == 2){
                    last[cur].add(new Node(i, j));
                }
            }
        }
        int minutes = 0;
        while (fresh != 0){
            if (last[cur].isEmpty()) return -1;

            last[cur^1].clear();
            for (int i = 0;  i < last[cur].size(); i++){
                Node node = last[cur].get(i);
                for (int j = 0 ; j < 4 ; j++){
                    int nx = node.x + dx[j];
                    int ny = node.y + dy[j];
                    if (0 <= nx && nx < n && 0 <= ny && ny < m && grid[nx][ny] == 1){
                        grid[nx][ny] = 2;
                        last[cur^1].add(new Node(nx, ny));
                        fresh --;
                    }
                }
            }
            cur ^= 1;
            minutes ++ ;
        }
        return minutes;
    }
}