SampleInterviewQuestions/rottingApples.cpp at main · ConnerOzenne/SampleInterviewQuestions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
#define R 4
#define C 5
using namespace std;

bool isvalid(int i, int j)
{
    return (i >= 0 && j >= 0 && i < R && j < C);
}

struct ele {
    int x, y;
}

bool isdelim(ele temp)
{
    return (temp.x == -1 && temp.y == -1);
}

bool checkall(int arr[][C])
{
    for (int i=0; i<R; i++)
       for (int j=0; j<C; j++)
          if (arr[i][j] == 1)
             return true;
    return false;
}

int rotOranges(int arr[][C])
{
    // Create a queue of cells
    queue<ele> Q;
    ele temp;
    int ans = 0;

    for (int i=0; i<R; i++)
    {
       for (int j=0; j<C; j++)
       {
            if (arr[i][j] == 2)
            {
                temp.x = i;
                temp.y = j;
                Q.push(temp);
            }
        }
    }

    temp.x = -1;
    temp.y = -1;
    Q.push(temp);

    while (!Q.empty())
    {
        bool flag = false;

        while (!isdelim(Q.front()))
        {
            temp = Q.front();

            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++;
                Q.push(temp);

                temp.x--;
            }

            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--;
                Q.push(temp);
                temp.x++;
            }

            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++;
                Q.push(temp);
                temp.y--;
            }

            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--;
                Q.push(temp);
            }

            Q.pop();
        }
        Q.pop();
        if (!Q.empty()) {
            temp.x = -1;
            temp.y = -1;
            Q.push(temp);
        }
    }

    return (checkall(arr))? -1: ans;

int main()
{
    int arr[][C] = { {2, 1, 0, 2, 1},
                     {1, 0, 1, 2, 1},
                     {0, 1, 1, 2, 1},
                     {1, 1, 0, 2, 1}};
    int ans = rotOranges(arr);
    if (ans == -1)
        cout << "All apple cannot rotten";
    else
         cout << "Time required for all apples to rot: " << ans << " days." << endl;
    return 0;
}