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++:
- #include <iostream>
- #include <bits/stdc++.h>
- using namespace std;
- int rottenOranges(int m,int n)
- {
- int a[m][n];
- queue<pair<int,int>> q;
- int p=0;
- for(int i=0;i<m;i++)
- {
- for(int j=0;j<n;j++)
- {
- cin>>a[i][j];
- if(a[i][j]==2)
- {
- q.push(make_pair(i,j));
- p++;
- }
- }
- }
- int t=0,x,y,c=0;
- while(p--)
- {
- x = q.front().first;
- y = q.front().second;
- if(a[x-1][y]==1&&x!=0)
- {
- q.push(make_pair(x-1,y));
- a[x-1][y]=2;
- t++;
- }
- if(a[x+1][y]==1&&x!=m-1)
- {
- q.push(make_pair(x+1,y));
- a[x+1][y]=2;
- t++;
- }
- if(a[x][y-1]==1&&y!=0)
- {
- q.push(make_pair(x,y-1));
- a[x][y-1]=2;
- t++;
- }
- if(a[x][y+1]==1&&y!=n-1)
- {
- q.push(make_pair(x,y+1));
- a[x][y+1]=2;
- t++;
- }
- q.pop();
- if(p==0&&t!=0)
- {
- p=t;
- t=0;
- c++;
- }
- }
- int k=0;
- for(int i=0;i<m;i++)
- {
- for(int j=0;j<n;j++)
- {
- if(a[i][j]==1)
- {
- return -1;
- }
- }
- }
- if(k==0)
- {
- return c;
- }
- }
- int main() {
- int t;
- cin>>t;
- while(t--)
- {
- int m,n;
- cin>>m;
- cin>>n;
- cout<<rottenOranges(m,n)<<endl;
- }
- return 0;
- }
Here is the Video: