Q16

#include<bits/stdc++.h>
#include<iostream>
#define R 3
#define C 5
using namespace std;

// function to check whether a cell is valid / invalid
bool isVALID(int x, int y)
{
    return (x >= 0 && y >= 0 && x < R && y < C);
}

// structure for storing coordinates of the cell
struct ele {
    int i, j;
};

// Function to check whether the cell is delimiter
// which is (-1, -1)
bool isdelim(ele temp)
{
    return (temp.i == -1 && temp.j == -1);
}

// Function to check whether there is still a fresh
// orange remaining
bool checkall(int arr[][C])
{
    for (int x=0; x<R; x++)
       for (int y=0; y<C; y++)
          if (arr[x][y] == 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
int rotOranges(int arr[][C])
{
    // Create a queue of cells
    queue<ele> Q;
    ele temp;
    int ans = 0;

    // Store all the cells having rotten orange in first time frame
    for (int x=0; x<R; x++)
    {
       for (int y=0; y<C; y++)
       {
            if (arr[x][y] == 2)
            {
                temp.i = x;
                temp.j = y;
                Q.push(temp);
            }
        }
    }

    // Separate these rotten oranges from the oranges which will rotten
    // due the oranges in first time frame using delimiter which is (-1, -1)
    temp.i = -1;
    temp.j = -1;
    Q.push(temp);

    // Process the grid while there are rotten oranges in the Queue
    while (!Q.empty())
    {
        // 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.front()))
        {
            temp = Q.front();

            // Check right adjacent cell that if it can be rotten
            if (isVALID(temp.i+1, temp.j) && arr[temp.i+1][temp.j] == 1)
            {
                // if this is the first orange to get rotten, increase
                // count and set the flag.
                if (!flag) ans++, flag = true;

                // Make the orange rotten
                arr[temp.i+1][temp.j] = 2;

                // push the adjacent orange to Queue
                temp.i++;
                Q.push(temp);

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

            // Check left adjacent cell that if it can be rotten
            if (isVALID(temp.i-1, temp.j) && arr[temp.i-1][temp.j] == 1) {
                if (!flag) ans++, flag = true;
                arr[temp.i-1][temp.j] = 2;
                temp.i--;
                Q.push(temp); // push this cell to Queue
                temp.i++;
            }

            // Check top adjacent cell that if it can be rotten
            if (isVALID(temp.i, temp.j+1) && arr[temp.i][temp.j+1] == 1) {
                if (!flag) ans++, flag = true;
                arr[temp.i][temp.j+1] = 2;
                temp.j++;
                Q.push(temp); // Push this cell to Queue
                temp.j--;
            }

            // Check bottom adjacent cell if it can be rotten
            if (isVALID(temp.i, temp.j-1) && arr[temp.i][temp.j-1] == 1) {
                if (!flag) ans++, flag = true;
                arr[temp.i][temp.j-1] = 2;
                temp.j--;
                Q.push(temp); // push this cell to Queue
            }

            Q.pop();
        }

        // Pop the delimiter
        Q.pop();

        // If oranges were rotten in current frame than separate the
        // rotten oranges using delimiter for the next frame for processing.
        if (!Q.empty()) {
            temp.i = -1;
            temp.j = -1;
            Q.push(temp);
        }

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

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

// Drive program
int main()
{
    int arr[100][C];
    for(int x=0;x<4;x++)
      for(int y=0;y<C;y++)
        cin>>arr[x][y];
    int ans = rotOranges(arr);
    if (ans == -1)
        cout <<"-1";
    else
         cout <<ans << endl;
    return 0;
}