Q:

Rotten Oranges

Given a matrix of dimension r*c where each cell in the matrix can have values 01 or 2 which has the following meaning:

• 0 : Empty cell
• 1 : Cells have fresh oranges
• 2 : Cells have rotten oranges

So, we have to determine what is the minimum time required to all oranges. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j][i+1,j][i,j-1][i,j+1] (up, down, left and right) in unit time. If it is impossible to rot every orange then simply return -1.

Example:

```    Input:
2
3 5
2 1 0 2 1 1 0 1 2 1 1 0 0 2 1

Output:
2```

Algorithm:

To implement this question we use BFS and a queue data structure.

1. At first, we push all positions into the queue which has 2 and make a partition by inserting NULL into the queue.
2. We pop every element from the queue until the first NULL comes and Go for its four neighbor's if there is any 1 then make it two and push it into the queue and separate this section again inserting a NULL into the queue.
3. Whenever we encounter NULL except for the first NULL and if it is not a last element of the queue then we increase the count value.
4. Repeat step 2 to 3 until the queue is empty.

C++ Implementation for Rotten Oranges problem

``````#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool zero(int *arr,int r,int c){
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(*((arr+i*c)+j)==1)
return false;
}
}
return true;
}

int rotten(int *arr,int r,int c){
queue<pair<int,int> >q;
int store=0,temp=0;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(*((arr+i*c)+j)==2){
q.push(make_pair(i,j));
}
}
}
q.push(make_pair(-1,-1));
while(!q.empty()){
pair<int,int> p=q.front();
q.pop();
if(p.first!=-1){
if(*((arr+p.first*c)+p.second)==1){
temp=1;
*((arr+p.first*c)+p.second)=2;
}
if(p.first==0 && p.second==0){
if(*((arr+(p.first+1)*c)+p.second)==1){
q.push(make_pair((p.first+1),p.second));
}
if(*((arr+(p.first)*c)+p.second+1)==1){
q.push(make_pair((p.first),p.second+1));
}
}
else if(p.first==0 && p.second==c-1){
if(*((arr+(p.first+1)*c)+p.second)==1){
q.push(make_pair((p.first+1),p.second));
}
if(*((arr+(p.first)*c)+p.second-1)==1){
q.push(make_pair((p.first),p.second-1));
}
}
else if(p.first==0){
if(*((arr+(p.first+1)*c)+p.second)==1){
q.push(make_pair((p.first+1),p.second));
}
if(*((arr+(p.first)*c)+p.second-1)==1){
q.push(make_pair((p.first),p.second-1));
}
if(*((arr+(p.first)*c)+p.second+1)==1){
q.push(make_pair((p.first),p.second+1));
}
}
else if(p.first==r-1 && p.second==0){
if(*((arr+(p.first-1)*c)+p.second)==1){
q.push(make_pair((p.first-1),p.second));
}
if(*((arr+(p.first)*c)+p.second+1)==1){
q.push(make_pair((p.first),p.second+1));
}
}
else if(p.second==0){
if(*((arr+(p.first-1)*c)+p.second)==1){
q.push(make_pair((p.first-1),p.second));
}
if(*((arr+(p.first+1)*c)+p.second)==1){
q.push(make_pair((p.first+1),p.second));
}
if(*((arr+(p.first)*c)+p.second+1)==1){
q.push(make_pair((p.first),p.second+1));
}
}
else if(p.first==r-1 && p.second==c-1){
if(*((arr+(p.first-1)*c)+p.second)==1){
q.push(make_pair((p.first-1),p.second));
}
if(*((arr+(p.first)*c)+p.second-1)==1){
q.push(make_pair((p.first),p.second-1));
}
}
else if(p.first==r-1){
if(*((arr+(p.first-1)*c)+p.second)==1){
q.push(make_pair((p.first-1),p.second));
}
if(*((arr+(p.first)*c)+p.second-1)==1){
q.push(make_pair((p.first),p.second-1));
}
if(*((arr+(p.first)*c)+p.second+1)==1){
q.push(make_pair((p.first),p.second+1));
}
}
else if(p.second==c-1){
if(*((arr+(p.first-1)*c)+p.second)==1){
q.push(make_pair((p.first-1),p.second));
}
if(*((arr+(p.first+1)*c)+p.second)==1){
q.push(make_pair((p.first+1),p.second));
}
if(*((arr+(p.first)*c)+p.second-1)==1){
q.push(make_pair((p.first),p.second-1));
}
}
else{
if(*((arr+(p.first)*c)+p.second-1)==1){
q.push(make_pair((p.first),p.second-1));
}
if(*((arr+(p.first)*c)+p.second+1)==1){
q.push(make_pair((p.first),p.second+1));
}
if(*((arr+(p.first-1)*c)+p.second)==1){
q.push(make_pair((p.first-1),p.second));
}
if(*((arr+(p.first+1)*c)+p.second)==1){
q.push(make_pair((p.first+1),p.second));
}
}
}
if(p.first==-1){
if(!q.empty()){
q.push(make_pair(-1,-1));
}
if(temp==1){
store++;
temp=0;
}
}
}
return store;
}

int main() {
int num;
cin>>num;

for(int i=0;i<num;i++){
int r,c;
cin>>r>>c;
int arr[r][c];
for(int j=0;j<r;j++){
for(int k=0;k<c;k++){
cin>>arr[j][k];
}
}

int store=rotten(&arr[0][0],r,c);
if(!zero(&arr[0][0],r,c))
cout<<"-1"<<endl;
else
cout<<store<<endl;
}

return 0;
}
``````

Output

`Number of days are : 2`