Rotten Oranges

Task: Given a M*N matrix, each cell in the matrix with the 0 or 1 0r 2 values which means:

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 in indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] ( up, down, left and right) in the unit time. If it is impossible to rot every orange then return -1.

Example:

1

3 5

2 1 0 2 1 1 0 1 2 1 1 0 0 2 1

Output:

2

---

Here is the Code:

Program in C++:

1. #include <iostream>
2. #include <bits/stdc++.h>
3. using namespace std;
4. int rottenOranges(int m,int n)
5. {
6.     int a[m][n];
7.     queue<pair<int,int>> q;
8.     int p=0;
9.     for(int i=0;i<m;i++)
10.     {
11.         for(int j=0;j<n;j++)
12.         {
13.             cin>>a[i][j];
14.             if(a[i][j]==2)
15.             {
16.                 q.push(make_pair(i,j));
17.                 p++;
18.             }
19.         }
20.     }
21.     int t=0,x,y,c=0;
22.     while(p--)
23.     {
24.         x = q.front().first;
25.         y = q.front().second;
26.         if(a[x-1][y]==1&&x!=0)
27.         {
28.             q.push(make_pair(x-1,y));
29.             a[x-1][y]=2;
30.             t++;
31.         }
32.         if(a[x+1][y]==1&&x!=m-1)
33.         {
34.             q.push(make_pair(x+1,y));
35.             a[x+1][y]=2;
36.             t++;
37.         }
38.         if(a[x][y-1]==1&&y!=0)
39.         {
40.             q.push(make_pair(x,y-1));
41.             a[x][y-1]=2;
42.             t++;
43.         }
44.         if(a[x][y+1]==1&&y!=n-1)
45.         {
46.             q.push(make_pair(x,y+1));
47.             a[x][y+1]=2;
48.             t++;
49.         }
50.         q.pop();
51.         if(p==0&&t!=0)
52.         {
53.             p=t;
54.             t=0;
55.             c++;
56.         }
57.     } 
58.     int k=0;
59.     for(int i=0;i<m;i++)
60.     {
61.         for(int j=0;j<n;j++)
62.         {
63.              if(a[i][j]==1)
64.              {
65.                  return -1;
66.              }
67.         }
68.     }
69.     if(k==0)
70.     {
71.         return c;
72.     }
73. }
74. int main() {
75. int t;
76. cin>>t;
77. while(t--)
78. {
79.     int m,n;
80.     cin>>m;
81.     cin>>n;
82.     cout<<rottenOranges(m,n)<<endl;
83.     
84. }
85. return 0;
86. }

---

Here is the Video:

---