class Solution {
public:

    void setNeighbors(vector<vector<int>>& grid, int x, int y){
        // set neighbors to 3 to trigger change
        if (x-1 >= 0 && grid[x-1][y] == 1){
            grid[x-1][y] = 3;
        }
        if (x+1 < grid.size() && grid[x+1][y] == 1){
            grid[x+1][y] = 3;
        }
        if (y-1 >= 0 && grid[x][y-1] == 1){
            grid[x][y-1] = 3;
        }
        if (y+1 < grid[0].size() && grid[x][y+1] == 1){
            grid[x][y+1] = 3;
        }
    }

    int orangesRotting(vector<vector<int>>& grid) {
        int minute = 0;
        bool allRotten = false;

        while (!allRotten){
            // check if all are rotten
            int fresh = 0;

            for (int i=0; i<grid.size(); i++){
                for (int j=0; j<grid[0].size(); j++){
                    if (grid[i][j] == 1 || grid[i][j] == 3){
                        fresh++;
                    }

                    if (grid[i][j] == 2){
                        setNeighbors(grid, i, j);
                    }
                }
            }

            if (fresh == 0){
                allRotten = true;
                break;
            }

            // make neighbours rotten from 3
            int changes = 0;
            for (int i=0; i<grid.size(); i++){
                for (int j=0; j<grid[0].size(); j++){
                    if (grid[i][j] == 3){
                        grid[i][j] = 2;
                        changes++;
                    }
                }
            }

            /* if nothing changes on the board and some fresh still remaining
              return impossible */
            if (changes == 0 && fresh > 0){
                return -1;
            }

            minute++;
        }

        return minute;
    }
};