Rotting Oranges

Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,

• 1 representing a fresh orange, or

• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10

• grid[i][j] is 0, 1, or 2.

Solutions

🧠 Cpp

class Solution
{    
enum state{empty, fresh, rotten};
public:
    template<state state_to_check>
    bool is_cell(int i, int j, vector<vector<int>>& grid)
    {
        try
        {
            return grid.at(i).at(j) == state_to_check;
        }
        catch(const std::out_of_range)
        {
            return true;
        }
    }

    bool check_siders_is_present(int i, int j, vector<vector<int>>& g)
    {
        bool is_present = is_cell<empty>(i,j,g) || is_cell<rotten>(i,j,g) ? true :
           !(is_cell<empty>(i+1,j,g) && is_cell<empty>(i-1,j,g) 
             && is_cell<empty>(i,j+1,g) && is_cell<empty>(i,j-1,g));
        return is_present;
    }

    int orangesRotting(vector<vector<int>>& g)
    {
        //input check
        //if(g.size() == 1 && g[0].size() ==1 )
          //  return g[0][0] == rotten ? 0 : -1;

        //there is no cut off oranges
        for(int i = 0; i < g.size(); i++)
        for(int j = 0; j < g[i].size(); j++)
            if(check_siders_is_present(i,j,g) == false)
                return -1;

        //there is at least one rotten
        bool rotten_is_present = false,
             fresh_is_present = false;
        for(auto line : g)
        {
            if(count(line.begin(), line.end(), rotten))
            {
                rotten_is_present = true;
            }
            if(count(line.begin(), line.end(), fresh))
            {
                fresh_is_present = true;
            }
        }
        if(!rotten_is_present)
            return fresh_is_present ? -1 : 0;

        //start iteration
        vector<vector<int>> grid(g);
        queue<pair<int,int>> to_rot;
        bool all_rotten = false;
        size_t minutes = 0;

        auto rot_if_fresh = [&grid, &all_rotten](int i, int j)
        {
            try
            {
                if (grid.at(i).at(j) == fresh)
                {
                    grid[i][j] = rotten;
                    all_rotten = false;
                }
            }
            catch(const std::out_of_range){}
        };

        while(!all_rotten)
        {
            all_rotten = true; 
            for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[i].size(); j++)
            {
                if(grid[i][j] == rotten)
                    to_rot.push({i,j});
            }

            while(!to_rot.empty()) 
            {
                auto p = to_rot.front(); to_rot.pop();

                int i = p.first, j = p.second;
                rot_if_fresh(i+1,j);
                rot_if_fresh(i-1,j);
                rot_if_fresh(i,j+1);
                rot_if_fresh(i,j-1);
            }

            if(!all_rotten)
                minutes++;

        }

        fresh_is_present = false;
        for(auto line : grid)
        if(count(line.begin(), line.end(), fresh))
        {
            fresh_is_present = true;
        }
        return fresh_is_present ? -1 : minutes;

    }
};