Minimum time required to rotten all oranges

// C# program to rot all oranges when you can move
// in all the four direction from a rotten orange
using System;
class GFG {

    static int R = 3;
    static int C = 5;

    // Check if i, j is under the array
    // limits of row and column
    static bool issafe(int i, int j)
    {
        if (i >= 0 && i < R && j >= 0 && j < C)
            return true;
        return false;
    }

    static int rotOranges(int[, ] v)
    {
        bool changed = false;
        int no = 2;
        while (true) {
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {

                    // Rot all other oranges present at
                    // (i+1, j), (i, j-1), (i, j+1), (i-1,
                    // j)
                    if (v[i, j] == no) {
                        if (issafe(i + 1, j)
                            && v[i + 1, j] == 1) {
                            v[i + 1, j] = v[i, j] + 1;
                            changed = true;
                        }
                        if (issafe(i, j + 1)
                            && v[i, j + 1] == 1) {
                            v[i, j + 1] = v[i, j] + 1;
                            changed = true;
                        }
                        if (issafe(i - 1, j)
                            && v[i - 1, j] == 1) {
                            v[i - 1, j] = v[i, j] + 1;
                            changed = true;
                        }
                        if (issafe(i, j - 1)
                            && v[i, j - 1] == 1) {
                            v[i, j - 1] = v[i, j] + 1;
                            changed = true;
                        }
                    }
                }
            }

            // if no rotten orange found it means all
            // oranges rottened now
            if (!changed)
                break;
            changed = false;
            no++;
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {

                // if any orange is found to be
                // not rotten then ans is not possible
                if (v[i, j] == 1)
                    return -1;
            }
        }

        // Because initial value for a rotten
        // orange was 2
        return no - 2;
    }

    static void Main()
    {

        int[, ] v = { { 2, 1, 0, 2, 1 },
                      { 1, 0, 1, 2, 1 },
                      { 1, 0, 0, 2, 1 } };

        Console.Write("Max time incurred: "
                      + rotOranges(v));
    }
}

// This code is contributed by divyeshrabadiya07

// C# program to find minimum time
// required to make all oranges rotten
using System;
using System.Collections.Generic;

class GFG {
    public const int R = 3;
    public const int C = 5;

    // structure for storing
    // coordinates of the cell
    public class Ele {
        public int x = 0;
        public int y = 0;
        public Ele(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

    // function to check whether a cell
    // is valid / invalid
    public static bool isValid(int i, int j)
    {
        return (i >= 0 && j >= 0 && i < R && j < C);
    }

    // Function to check whether the cell
    // is delimiter which is (-1, -1)
    public static bool isDelim(Ele temp)
    {
        return (temp.x == -1 && temp.y == -1);
    }

    // Function to check whether there
    // is still a fresh orange remaining
    public static bool checkAll(int[][] arr)
    {
        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
    public static int rotOranges(int[][] arr)
    {
        // Create a queue of cells
        LinkedList<Ele> Q = new LinkedList<Ele>();
        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) {
                    Q.AddLast(new Ele(i, j));
                }
            }
        }

        // Separate these rotten oranges from
        // the oranges which will rotten
        // due the oranges in first time frame
        // using delimiter which is (-1, -1)
        Q.AddLast(new Ele(-1, -1));

        // Process the grid while there are
        // rotten oranges in the Queue
        while (Q.Count > 0) {
            // 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.First.Value)) {
                temp = Q.First.Value;

                // 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 (!flag) {
                        // if this is the first orange
                        // to get rotten, increase
                        // count and set the flag.
                        ans++;
                        flag = true;
                    }

                    // Make the orange rotten
                    arr[temp.x + 1][temp.y] = 2;

                    // push the adjacent orange to Queue
                    temp.x++;
                    Q.AddLast(new Ele(temp.x, temp.y));

                    // Move back to current cell
                    temp.x--;
                }

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

                    // push this cell to Queue
                    Q.AddLast(new Ele(temp.x, temp.y));
                    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++;

                    // Push this cell to Queue
                    Q.AddLast(new Ele(temp.x, temp.y));
                    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--;

                    // push this cell to Queue
                    Q.AddLast(new Ele(temp.x, temp.y));
                }
                Q.RemoveFirst();
            }

            // Pop the delimiter
            Q.RemoveFirst();

            // If oranges were rotten in current
            // frame than separate the rotten
            // oranges using delimiter for the
            // next frame for processing.
            if (Q.Count > 0) {
                Q.AddLast(new Ele(-1, -1));
            }

            // If Queue was empty than no rotten
            // oranges left to process so exit
        }

        // Return -1 if all arranges could
        // not rot, otherwise ans
        return (checkAll(arr)) ? -1 : ans;
    }

    // Driver Code
    public static void Main(string[] args)
    {
        int[][] arr
            = new int[][] { new int[] { 2, 1, 0, 2, 1 },
                            new int[] { 1, 0, 1, 2, 1 },
                            new int[] { 1, 0, 0, 2, 1 } };

        int ans = rotOranges(arr);
        if (ans == -1) {
            Console.WriteLine("All oranges cannot rot");
        }
        else {
            Console.WriteLine("Time required for all "
                              + "oranges to rot => " + ans);
        }
    }
}

// This code is contributed by Shrikant13