Rotten Oranges Problem

Given a Matrix of order M*N, where each cell can have zero or one orange. The orange in the cell (if present) can be either fresh or rotten. A rotten orange will rot the fresh oranges in the nearby cell in unit time. If a rotten orange is in cell (i,j), then it will rot the fresh oranges present in cells

(i+1, j) (i-1, j) (i, j+1) (i, j-1)

in unit time (say one minute). If a fresh orange is surrounded by all empty cells then it cannot be rotten at all. Given the below matrix

{{2, 1, 0, 2, 1}
 {1, 0, 1, 2, 1}
 {0, 0, 0, 2, 1} }

Where

0 - Empty Cell
1 - Fresh Orange
2 - Rotten Orange

Then all the oranges will rot in unit time. If the input matrix is

{{2, 1, 0, 1, 1}
 {1, 0, 1, 1, 1}
 {1, 1, 1, 1, 1} }

Then it will take 8 time to rot all the oranges in the matrix.
If the Matrix is as below

{{2, 1, 0, 2, 1}
 {0, 0, 1, 2, 1}
 {1, 0, 0, 2, 1} }

Then the entire matrix can never be rotten, because the orange in cell (2, 0) will always be fresh.
Write a function that accepts a two dimensional matrix having values 0, 1 and 2 representing the state of oranges in the cell and return the time in which entire matrix will rot. If all the oranges in the matrix cannot be rotten, then the function should return -1 to indicate the same.

Algorithm

The solution of this problem is similar to BFS (or level order traversal of Binary Tree).  We use a Queue data structure and insert cell in queue. The structure that gets stored in the queue (the data part of queue) is

struct DataElement
{
    int i;
    int j;
    int time;
};

The time in this structure is the time at which orange in this cell will rot. Initially time is zero and all the cells with rotten oranges are inserted in the Queue (with their time as zero) After the the below algorithm is used

WHILE (Queue is not empty)
  Remove cell from Queue and check all the nearby cells of this removed cell.
     IF the nearby cell has Fresh orange
         Insert it in the Queue with time = time of removed cell +1

Time of the last cell removed from the queue represent the time to rot all oranges in the queue. After this loop we also need to check if there is some cell in the matrix that still has 1. If such cell is present, then this cell is not reachable from any of the rotten orange’s cell. In this case we need to return -1.
 
 

Video

Code

1. main.cpp

#include "MyQueue.hpp"
#define M 3
#define N 5
#define FRESH 1
#define ROTTEN 2
int timeToRot(int orange[M][N])
{
    MyQueue queue;
    int curTime = 0;
    // INSERTING ALL ROTTEN ORANGES
    for(int i=0; i<M; i++)
        for(int j=0; j<N; j++)
            if(orange[i][j] == ROTTEN)
            {
                queue.insert(NodeElement(i, j, curTime));
            }
    while(!queue.isEmpty())
    {
        NodeElement ne = queue.remove();
        curTime = ne.time;
        if(ne.i+1=0 && orange[ne.i-1][ne.j] == FRESH)
        {
            orange[ne.i-1][ne.j] = ROTTEN;
            queue.insert(NodeElement(ne.i-1, ne.j, curTime+1));
        }
        if(ne.j-1>=0 && orange[ne.i][ne.j-1] == FRESH)
        {
            orange[ne.i][ne.j-1] = ROTTEN;
            queue.insert(NodeElement(ne.i, ne.j-1, curTime+1));
        }
    }
    // Check if some fresh oranges left in the matrix
    for(int i=0; i<M; i++)
        for(int j=0; j<N; j++)
            if(orange[i][j] == FRESH)
            {
                return -1;
            }
    return curTime;
}
int main()
{
    int orange[M][N] = {
        {2, 1, 0, 1, 1},
        {1, 0, 2, 1, 1},
        {1, 1, 1, 1, 1} };
    printf("Time To Rot: %d\n", timeToRot(orange));
    return 0;
}

MyQueue.hpp

#ifndef MyQueue_hpp
#define MyQueue_hpp
#include
struct NodeElement
{
    int i;
    int j;
    int time;
    NodeElement():i(-1), j(-1), time(-1){}
    NodeElement(int vi, int vj, int vtime):i(vi), j(vj), time(vtime){}
};
struct Node
{
    NodeElement data;
    Node* next;
    Node(NodeElement v):data(v), next(NULL){}
};
class MyQueue{
    Node* front;
    Node* end;
public:
    MyQueue():front(NULL), end(NULL){}
    void insert(NodeElement v);
    NodeElement remove();
    bool isEmpty();
};
#endif /* MyQueue_hpp */

MyQueue.cpp

#include "MyQueue.hpp"
void MyQueue::insert(NodeElement v)
{
    Node* temp = new Node(v);
    if(end == NULL)
    {
        front = end = temp;
    }
    else
    {
        end->next = temp;
        end = temp;
    }
}
NodeElement MyQueue::remove()
{
    NodeElement v;
    if(!isEmpty()){
        Node* temp = front;
        front = front->next;
        v.i = temp->data.i;
        v.j = temp->data.j;
        v.time = temp->data.time;
        delete temp;
        if(front == NULL){
            end = NULL;
        }
    }
    return v;
}
bool MyQueue::isEmpty()
{
    return (front == NULL);
}