C Program for Rotten Orange Problem with Queues

The rotten oranges is a very famous topic in the DSA world which is usually solved in higher-level programming languages like java or python and in some cases Cpp with templates although throughout the internet there is no code for the same in C language, but you do not have to worry this blog will provide you that.

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int front = -1, rear = -1;

struct Queue
{
    int i;
    int j;
    int time;
} queue[10000];

void push(int i, int j, int t)
{
    if (rear == 10000 - 1)
    {
        printf("Queue is full.\n");
    }
    else
    {
        rear++;
        queue[rear].i = i;
        queue[rear].j = j;
        queue[rear].time = t;
    }
}

void pop(int *i, int *j, int *t)
{
    if (front == rear)
    {
        printf("Queue is empty.\n");
    }
    else
    {
        front++;
        *i = queue[front].i;
        *j = queue[front].j;
        *t = queue[front].time;
    }
}

int main()
{
    int t, r, c, time = 0, drow[4] = {-1, 0, 0, 1}, dcol[4] = {0, -1, 1, 0};
    bool flag = false;

    printf("Enter the number of test cases --> ");
    scanf("%d", &t);

    for (int i = 0; i < t; i++)
    {
        printf("Enter the number of rows and columns respectively for test case %d-->", i + 1);
        scanf("%d%d", &r, &c);
        int matrix[r][c];

        printf("Fill the spaces in the matrix\t \"0\" for empty space  \"1\" for fresh orange  \"2\" for rotten orange\n");
        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                scanf("%d", &matrix[i][j]);
                if (matrix[i][j] == 2)
                {
                    push(i, j, 0);
                }
            }
        }

        while (front != rear && rear != -1)
        {
            int i_index, j_index, neighbour_r, neighbour_c;
            pop(&i_index, &j_index, &time);

            for (int i = 0; i < 4; i++)
            {
                neighbour_r = i_index + drow[i];
                neighbour_c = j_index + dcol[i];
                if (neighbour_r >= 0 && neighbour_r < r && neighbour_c >= 0 && neighbour_c < c && matrix[neighbour_r][neighbour_c] == 1)
                {
                    matrix[neighbour_r][neighbour_c] = 2;
                    push(neighbour_r, neighbour_c, time + 1);
                }
            }
        }

        flag = true;
        for (int i = 0; i < r; i++)
        {
            for (int j = 0; j < c; j++)
            {
                if (matrix[i][j] == 1)
                {
                    flag = false;
                    break;
                }
            }
            if (!flag)
            {
                break;
            }
        }

        if (flag)
        {
            printf("The time required to rot all the oranges is %d\n", time);
        }
        else
        {
            printf("-1\n");
        }
    }
    return 0;
}

Explanation:

This code is an implementation of a problem that involves a matrix representing oranges. The problem is to find the time required to rot all the oranges. The code uses a Breadth First Search (BFS) algorithm to solve the problem.

The program starts by including three header files: "stdio.h" for input and output, "stdbool.h" for boolean variables and "stdlib.h" for standard library functions. The program also declares two variables "front" and "rear" to represent the front and rear indices of a queue. These indices are used to implement the BFS algorithm.

Next, a structure named "Queue" is defined with three variables: "i" and "j" represent the row and column indices of an orange, and "time" represents the time when the orange was added to the queue.

The program defines two functions, "push" and "pop", to perform operations on the queue. The "push" function adds an orange to the rear of the queue, and the "pop" function removes an orange from the front of the queue. The program also defines a global array named "queue" of the "Queue" structure to store the oranges.

The main function of the program is executed when the program is run. The main function first declares several variables, including "t" to represent the number of test cases, "r" and "c" to represent the number of rows and columns in the matrix, "time" to represent the time required to rot all the oranges, and two arrays "drow" and "dcol" to represent the four directions of the BFS algorithm.

The program prompts the user to enter the number of test cases, and then enters a loop that runs "t" times. In each iteration, the program prompts the user to enter the number of rows and columns in the matrix and then creates a two-dimensional array named "matrix" to represent the oranges.

The program prompts the user to fill in the spaces in the matrix. The user is instructed to enter "0" for an empty space, "1" for a fresh orange, and "2" for a rotten orange. If an orange is rotten, the "push" function is called to add the orange to the queue.

The program then enters a loop that runs until the front and rear indices of the queue are the same and the rear index is not equal to -1. Inside the loop, the "pop" function is called to remove an orange from the queue. The program then checks the four neighboring cells of the orange using the "drow" and "dcol" arrays. If a neighboring cell is a fresh orange, the cell is changed to a rotten orange and the "push" function is called to add the cell to the queue with the time increased by 1.

After the BFS algorithm is completed, the program checks whether all the oranges are rotten. If all the oranges are rotten, the time required to rot all the oranges is printed on the console. If there are any fresh oranges left, the program prints "-1" to the console.

In summary, the program reads a matrix of oranges, uses a BFS algorithm to calculate the time required to rot all the oranges, and then outputs the time or "-1" if there are any fresh oranges left.

Rotten Oranges in C

Explanation: