14.Rotting Oranges

In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;

• the value 1 representing a fresh orange;

• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.

Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:
Input: [[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: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Solution: (Queue + BFS)

Approach: There can be multiple '2'/ Starting point . So we initially push all the '2' in a queue and Perform BFS with time

class Solution
{
public:
    int bfs(vector<vector<int>> &grid, queue<pair<int, pair<int, int>>> q)
    {

        int n = grid.size();
        int m = grid[0].size();

        int time = 0;

        while (!q.empty())
        {
            time = q.front().first;
            int i = q.front().second.first;
            int j = q.front().second.second;

            q.pop();

            if (i - 1 >= 0 && grid[i - 1][j] == 1)
            {
                q.push({time + 1, {i - 1, j}});
                grid[i - 1][j] = 2;
            }

            if (i + 1 < n && grid[i + 1][j] == 1)
            {
                q.push({time + 1, {i + 1, j}});
                grid[i + 1][j] = 2;
            }

            if (j - 1 >= 0 && grid[i][j - 1] == 1)
            {
                q.push({time + 1, {i, j - 1}});
                grid[i][j - 1] = 2;
            }

            if (j + 1 < m && grid[i][j + 1] == 1)
            {
                q.push({time + 1, {i, j + 1}});
                grid[i][j + 1] = 2;
            }
        }
        return time;
    }

    int orangesRotting(vector<vector<int>> &grid)
    {

        int n = grid.size();
        int m = grid[0].size();

        queue<pair<int, pair<int, int>>> q;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (grid[i][j] == 2)
                {
                    q.push({0, {i, j}});
                }
            }
        }

        int count = bfs(grid, q);

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

        return count;
    }
};