rottentomatoes.c

/*Given a grid of dimension nxm where each cell in the grid can have values 0, 1 or 2 which has the
 following meaning:
0 : Empty cell
1 : Cells have fresh oranges
2 : Cells have rotten oranges

We have to determine what is the minimum time required to rot 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.*/

/*Input: grid = {{0,1,2},{0,1,2},{2,1,1}}
Output: 1
Explanation: The grid is-
0 1 2
0 1 2
2 1 1
Oranges at positions (0,2), (1,2), (2,0)
will rot oranges at (0,1), (1,1), (2,2) and
(2,1) in unit time*/

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAX 50
#define initial 1
#define visited 2
int adj[MAX][MAX];
int queue[MAX],front = -1, rear = -1;
int state[MAX],n;
void insert_queue(int vertex);
int isempty_queue();
int delete_queue();
void printarray(int * ptr);
void  make_adjacency_matrix(int * array);
int BFS(int * array);

int main()
{   int *array,i,j,pop,time;
    int rotten = 0;
    printf("\nEnter n for n*n matrics: ");
    scanf("%d", &n);
    array = calloc(n*n,sizeof(int));
    printf("\nPlease enter elment of matrix: \n");
    for(i=0;i<n*n;i++)
        {
            printf("Enter element no %d: ",i+1);
            scanf("%d",&array[i]);
        }
    printf("\nThe tomatoes in beginning is following: \n");
    printarray(array);

    make_adjacency_matrix(array);

   /* printf("\nThe adjacency matrix is: \n");
    for(i=0;i<n*n;i++)
    {
           for(j=0;j<4;j++)
                printf("%d ",adj[i][j]);
            printf("\n");
    }*/
    /*change state of all elements to initial*/
    for(i=0;i<n*n;i++)
        state[i] = 1;



    /*Search for all rotten tomatoes in array initially*/
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
           if(array[i*n + j]==2)
            {   /*since rotten found put its place-value inside queue and change its state from initial to visited*/
                /*place value tells us which particular tomatoes is rotten*/
                insert_queue(i*n + j);
                state[i*n + j] = 2;
            }
            /*Now after putting all rotten tomatoes in queue put an delimiter (-1) */
            /*delimiter differentiate between the tomatoes rotten first day and the next day and so on...*/
            /*tomatoes before delimiter is previous day rotten and after the delimiter are next day rotten*/
            insert_queue(-1);

           time = BFS(array);

           /*Now check whether all tomatoes are rotten or not*/
           /*If all rotten then tell the number of days in which all tomatoes are rotten*/

    for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                {
                    if(array[i*n + j] == 1)
                        {    rotten++;
                            break;
                        }
                }
            if(rotten)
                break;
        }
    if(rotten)
        printf("\nAll tomato will not be rotten:  ");
    else
        printf("\n All tomatoes will be rotten in %d days: ",time);


 free(array);
return 0;
}//main

/*Main ends here and below is the definition of all the function being used*/

void  make_adjacency_matrix(int * array)
    {
        int i,j;
            for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
        /*check adjacency only when there is tomato. (means array[i][j] != 0)*/
                {   if(array[i*n + j]!= 0)

                    {    //check left adjacency
            /*if j=0 then it will be first column and no element in left possible*/
            /*if it is not first column then check the left element it must be non-zero*/
                         if(j!=0 && array[i*n + (j-1)] != 0)
                            adj[i*n + j][0] = 1;

                        //check right adjacency
            /*if j=n-1 then it will be last column and no element in right side possible*/
            /*if it is not last column then check the right element and it must be non-zero*/
                        if(j!=n-1 && array[i*n + (j+1)]!=0)
                            adj[i*n + j][1] = 1;

                        //check up adjacency
            /*if i=0 then it will be first row and no element in upside possible*/
            /*if it is not the first row then check the upside element it must be non-zero*/
                        if(i!=0 && array[(i-1)*n + j]!=0)
                            adj[i*n + j][2] = 1;

                        //check down adjacency
            /*if i=n-1 then it will be last row and no element in downside possible*/
            /*if it is not the last row then chech the downside element it must be non-zero*/
                        if(i!= n-1 && array[(i+1)*n + j]!= 0)
                            adj[i*n + j][3] = 1;

                     }
                }
        }//end of for loop
    }//end of make adjacency matrix

int BFS(int * array)
    {
         int time=0,pop,i,j;
         while(!isempty_queue())
        {
           pop = delete_queue();
           if(pop == -1)
           { /*if queue is  empty do nothing*/
            if(!isempty_queue())//after popping delimiter if there is some element still in queue then..
                {   time++;
                    insert_queue(-1);
                    printf("\nTomatoes after %d day: \n",time);
                    printarray(array);
                }

           }
           /*check all adjacency (left,right,up,down)*/
           /*Since only 4 adjacency possible for any element hence loop operate for 4 time only*/
           for(j=0;j<4;j++)
            {
                if(adj[pop][j] == 1)//if adjacency found then..
                /*check whether it is left,right,up or downside adjacency*/

                    {   if(j==0 && state[pop-1] == initial)//for left adjacency, j=0 indicate left adjacency
                            {   array[pop - 1] = 2;
                                state[pop - 1] = visited;
                                insert_queue(pop - 1);
                            }
                        if(j==1 && state[pop+1] == initial)//for right adjacency
                            {   array[pop + 1] = 2;
                                state[pop + 1] = visited;
                                insert_queue(pop + 1);
                            }
                        if(j==2 && state[pop-n] == initial)//for up adjacency
                            {   array[pop - n] = 2;
                                state[pop - n] = visited;
                                insert_queue(pop - n);
                            }
                        if(j==3 && state[pop+n] == initial)//for down adjacency
                            {   array[pop + n] = 2;
                                state[pop + n] = visited;
                                insert_queue(pop + n);
                            }


             }//j loop printf("\n*****\n");


        }
    }
    return time;
    }//end of BFS

void printarray(int * ptr)
    {   int i ,j;
         for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                printf("%2d ",ptr[i*n + j]);
                printf("\n");
        }
    }

void insert_queue(int vertex)
    {
        if(rear == MAX-1)
            printf("queue overflown: \n");
        else
            {
                if(front == -1)//check if queue is empty
                    front++;//or front = 0;
                rear++;
                queue[rear] = vertex;
            }
    }//end of insert_queue

int isempty_queue()
    {
        if(front == -1 || front>rear)
            return 1;
        else
            return 0;
    }//end of isempty_queue

int delete_queue()
    {
        int deleted_item;
        /*front = -1 means (virgin queue) no value has been inserted yet in queue hence it is empty */
        /*front>rear means some value had been inserted in queue but now all had been taken outside hence queue is empty*/
        if(front == -1 || front>rear)
            {
                printf("\nQueue is underflown: ");
                exit(1);
            }
        deleted_item = queue[front];
        front++;
        return deleted_item;

    }//end of delete_queue