#994.Rotting Oranges [LeetCode Grind 75 in Java]

class State{
    int n;
    int time;

    public State(int n, int time){
        this.n = n;
        this.time = time;
    }
}

class Solution {
    private int[][] dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    public int orangesRotting(int[][] grid) {

        Queue<State> q = new LinkedList<>();
        int r = grid.length;
        int c = grid[0].length;

        for(int i = 0; i < r; i ++){
            for(int j = 0; j < c; j ++){
                if(grid[i][j] == 2){
                    int n = i * c + j;
                    q.add(new State(n, 0));
                } 
            }
        }

        int time = 0;

        while(!q.isEmpty()){
            int sz = q.size();

            while(sz -- > 0){
                State cn = q.poll();
                int cnr = cn.n / c;
                int cnc = cn.n % c;

                for(int d = 0; d < 4; d ++){
                    int nnr = cnr + dir[d][0];
                    int nnc = cnc + dir[d][1];

                    if(nnr >= 0 && nnc >= 0 && nnr < r && nnc < c){
                        if(grid[nnr][nnc] == 1){
                            grid[nnr][nnc] = 2;
                            int nn = nnr * c + nnc;
                            time = cn.time + 1;

                            q.add(new State(nn, time));
                        }
                    }
                }
            }
        }

        for(int i = 0; i < r; i ++){
            for(int j = 0; j < c; j ++){
                if(grid[i][j] == 1) return -1;
            }
        }

        return time;  
    }
}