QUESTION

Given a matrix of dimension m*n (m=3,n=5) where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:\n\n0: Empty cell\n\n1: Cells have fresh oranges\n\n2: Cells have rotten oranges.

“TESTCASE_1”: “2 1 0 2 1\n1 0 1 2 1\n1 0 0 2 1\n###—###SEPERATOR—###—\n2”, “TESTCASE_2”: “2 1 0 2 1\n0 0 1 2 1\n1 0 0 2 1\n###—###SEPERATOR—###—\nAll oranges cannot rot”, “TESTCASE_3”: “2 0 0 1 2\n1 0 0 2 1\n1 1 1 0 2\n###—###SEPERATOR—###—\n4”, “TESTCASE_4”: “2 2 2 1 1\n0 0 0 0 0\n1 1 1 1 1\n###—###SEPERATOR—###—\nAll oranges cannot rot”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

// C++ program to find minimum time required to make all
// oranges rotten
#include<bits/stdc++.h>
#define R 3
#define C 5
using namespace std;
 
// function to check whether a cell is valid / invalid
bool isvalid(int i, int j)
{
    return (i >= 0 && j >= 0 && i < R && j < C);
}
 
// structure for storing coordinates of the cell
struct ele {
    int x, y;
};
 
// Function to check whether the cell is delimiter
// which is (-1, -1)
bool isdelim(ele temp)
{
    return (temp.x == -1 && temp.y == -1);
}
 
// Function to check whether there is still a fresh
// orange remaining
bool checkall(int arr[][C])
{
    for (int i=0; i<R; i++)
       for (int j=0; j<C; j++)
          if (arr[i][j] == 1)
             return true;
    return false;
}
 
// This function finds if it is possible to rot all oranges or not.
// If possible, then it returns minimum time required to rot all,
// otherwise returns -1
int rotOranges(int arr[][C])
{
    // Create a queue of cells
    queue<ele> Q;
    ele temp;
    int ans = 0;
 
    // Store all the cells having rotten orange in first time frame
    for (int i=0; i<R; i++)
    {
       for (int j=0; j<C; j++)
       {
            if (arr[i][j] == 2)
            {
                temp.x = i;
                temp.y = j;
                Q.push(temp);
            }
        }
    }
 
    // Separate these rotten oranges from the oranges which will rotten
    // due the oranges in first time frame using delimiter which is (-1, -1)
    temp.x = -1;
    temp.y = -1;
    Q.push(temp);
 
    // Process the grid while there are rotten oranges in the Queue
    while (!Q.empty())
    {
        // This flag is used to determine whether even a single fresh
        // orange gets rotten due to rotten oranges in current time
        // frame so we can increase the count of the required time.
        bool flag = false;
 
        // Process all the rotten oranges in current time frame.
        while (!isdelim(Q.front()))
        {
            temp = Q.front();
 
            // Check right adjacent cell that if it can be rotten
            if (isvalid(temp.x+1, temp.y) && arr[temp.x+1][temp.y] == 1)
            {
                // if this is the first orange to get rotten, increase
                // count and set the flag.
                if (!flag) ans++, flag = true;
 
                // Make the orange rotten
                arr[temp.x+1][temp.y] = 2;
 
                // push the adjacent orange to Queue
                temp.x++;
                Q.push(temp);
 
                temp.x--; // Move back to current cell
            }
 
            // Check left adjacent cell that if it can be rotten
            if (isvalid(temp.x-1, temp.y) && arr[temp.x-1][temp.y] == 1) {
                if (!flag) ans++, flag = true;
                arr[temp.x-1][temp.y] = 2;
                temp.x--;
                Q.push(temp); // push this cell to Queue
                temp.x++;
            }
 
            // Check top adjacent cell that if it can be rotten
            if (isvalid(temp.x, temp.y+1) && arr[temp.x][temp.y+1] == 1) {
                if (!flag) ans++, flag = true;
                arr[temp.x][temp.y+1] = 2;
                temp.y++;
                Q.push(temp); // Push this cell to Queue
                temp.y--;
            }
 
            // Check bottom adjacent cell if it can be rotten
            if (isvalid(temp.x, temp.y-1) && arr[temp.x][temp.y-1] == 1) {
                if (!flag) ans++, flag = true;
                arr[temp.x][temp.y-1] = 2;
                temp.y--;
                Q.push(temp); // push this cell to Queue
            }
 
            Q.pop();
        }
 
        // Pop the delimiter
        Q.pop();
 
        // If oranges were rotten in current frame than separate the
        // rotten oranges using delimiter for the next frame for processing.
        if (!Q.empty()) {
            temp.x = -1;
            temp.y = -1;
            Q.push(temp);
        }
 
        // If Queue was empty than no rotten oranges left to process so exit
    }
 
    // Return -1 if all arranges could not rot, otherwise -1.
    return (checkall(arr))?-1: ans;
}
 
// Drive program
int main()
{
    int arr[3][5];
  	for(int i=0;i<3;i++)
      for(int j=0;j<5;j++)
        cin>>arr[i][j];
    int ans = rotOranges(arr);
    if (ans == -1)
        cout << "All oranges cannot rot";
    else
         cout << ans << endl;
    return 0;
}