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;
}