Rotten Oranges Problem

// C++ program to find minimum time required to make all 
// oranges rotten 
#include<bits/stdc++.h> 
#define R 3 
#define C 5 
using namespace std; 

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

// structure for storing coordinates of the cell 
struct ele { 
	int x, y; 
}; 

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

// Function to check whether there is still a fresh 
// orange remaining 
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; 
} 

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

	// Separate these rotten oranges from the oranges which will rotten 
	// due the oranges in first time frame using delimiter which is (-1, -1) 
	temp.x = -1; 
	temp.y = -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.x+1, temp.y) && arr[temp.x+1][temp.y] == 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.x+1][temp.y] = 2; 

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

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

			// 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--; 
				Q.push(temp); // push this cell to Queue 
				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++; 
				Q.push(temp); // Push this cell to Queue 
				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--; 
				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.x = -1; 
			temp.y = -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[][C] = { {2, 1, 0, 2, 1}, 
					{1, 0, 1, 2, 1}, 
					{1, 0, 0, 2, 1}}; 
	int ans = rotOranges(arr); 
	if (ans == -1) 
		cout << "All oranges cannot rotn"; 
	else
		cout << "Time required for all oranges to rot => " << ans << endl; 
	return 0; 
} 

At line 61, what if we make a queue of tuple with 3 int values, first being time-stamp, second for x-coordinate and y for y-coordinate. Do we still need to push the delimeter to separate the oranges from current time-frame? because now we will have time frame in the first value of queue tuple.

JUST USE BSF ....

int t;
cin >> t;
while (t--)
{
	int r, c;
	cin >> r >> c;

	int arr[r][c];

	for (int i = 0; i < r; i++)
	{
		for (int j = 0; j < c; j++)
			cin >> arr[i][j];
	}


	queue <pair<pair<int, int>, int>> q;



	int dx[4] = {0, 0, -1, 1};
	int dy[4] = { -1, 1, 0, 0};

	int vis[r][c];
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			vis[i][j] = 0;



	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			if (arr[i][j] == 2)
				q.push({{i, j}, 0}) , vis[i][j] = 1;


	int timeUnivers = -1;


	while (!q.empty())
	{

		auto f = q.front();
		int x = f.first.first;
		int y = f.first.second;
		int time = f.second;


		for (int i = 0; i < 4; i++)
		{
			int xi = x + dx[i] , yi = y + dy[i];

			if ((xi >= 0 && xi < r) && (yi >= 0 && yi < c) && vis[xi][yi] == 0)
			{

				if (arr[xi][yi] == 1)
				{
					arr[xi][yi] = 2;
					vis[xi][yi] = 1;
					q.push({{xi, yi}, time + 1});
					timeUnivers = time + 1;
				}
				else
				{
					vis[xi][yi] = 1;
				}


			}


		}
		q.pop();



	}




	bool f = true;
	for (int i = 0; i < r; i++)
	{	for (int j = 0; j < c; j++)
		{	if (arr[i][j] == 1)
			{
				cout << "-1" << endl;
				f = false;
				break;
			}
		}
		if (!f)
			break;
	}



	if (f)
		cout << timeUnivers << endl;







}

Bruteforce solution works as well.

#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends

class Solution
{
public:
//Function to find minimum time required to rot all oranges.

int mx[4] = {-1, 0, 1, 0};
int my[4] = {0, 1, 0, -1};

inline bool validPos(int x, int y, int n, int m) {
    return (x >= 0 && x < n && y >= 0 && y < m);
}
    
    
struct NodeBfs
{
    int i, j, t;
    NodeBfs(int i, int j, int t) : i(i), j(j), t(t) {}
};

int orangesRotting(vector<vector<int>>& grid) {
    
    int n = grid.size();
    int m = grid[0].size();
    
    queue<NodeBfs> q;
    
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 2) {
                q.push(NodeBfs(i, j, 0));
            }
        }
    }
    
    int maxTime = 0;
    
    while (!q.empty())
    {
        NodeBfs curr = q.front();
        q.pop();

        int x = curr.i;
        int y = curr.j;

        maxTime = curr.t;

        for (int p = 0; p < 4; p++)
        {
            int nx = x + mx[p];
            int ny = y + my[p];
            if (validPos(nx, ny, n, m) && grid[nx][ny] == 1)
            {
                grid[nx][ny] = 2;
                q.push(NodeBfs(nx, ny, curr.t + 1));
            }
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 1) {
                return -1;
            }
        }
    }
    
    return maxTime;
}


// // BRUTE FORCE
// int orangesRotting(vector<vector<int>>& grid) {
//     int n = grid.size();
//     int m = grid[0].size();
    
//     int t = 0;
    
//     while(true) {
        
//         int cnt = 0;
//         for(int i = 0; i < n; i++) {
//             for(int j = 0; j < m; j++) {
//                 if(grid[i][j] == 2) {
//                     for(int p = 0; p < 4; p++) {
//                         int nx = i+mx[p];
//                         int ny = j+my[p];
//                         if(validPos(nx, ny, n, m) && grid[nx][ny] == 1) {
//                             grid[nx][ny] = -1;
//                             cnt += 1;
//                         }
//                     }
//                 }
//             }
//         }
        
//         for(int i = 0; i < n; i++) {
//             for(int j = 0; j < m; j++) {
//                 grid[i][j] = (grid[i][j] == -1 ? 2 : grid[i][j]);
//             }
//         }
        
//         if(cnt == 0) {
//             break;
//         }
        
//         t += 1;
//     }
    
//     // for(int i = 0; i < n; i++) {
//     //     for(int j = 0; j < m; j++) {
//     //         cout << grid[i][j] << " ";
//     //     }
//     //     cout << endl;
//     // }
    
//     for(int i = 0; i < n; i++) {
//         for(int j = 0; j < m; j++) {
//             if(grid[i][j] == 1) {
//                 return -1;
//             }
//         }
//     }
    
//     return t;
// }

};

// { Driver Code Starts.
int main(){
int tc;
cin >> tc;
while(tc--){
int n, m;
cin >> n >> m;
vector<vector>grid(n, vector(m, -1));
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> grid[i][j];
}
}
Solution obj;
int ans = obj.orangesRotting(grid);
cout << ans << "\n";
}
return 0;
} // } Driver Code Ends

class Solution
{
class Orange{
int timeframe;
int x,y;
Orange(int timeframe,int x,int y)
{
this.timeframe = timeframe;
this.x = x;
this.y = y;
}
}
//Function to find minimum time required to rot all oranges.
boolean isvalid(int i, int j,int r,int c)
{
return (i >= 0 && j >= 0 && i < r && j < c);
}

boolean checkall(int arr[][],int r,int c) 
{ 
	for (int i=0; i<r; i++) 
	{
    	for (int j=0; j<c; j++) 
    	{
    		if (arr[i][j] == 1) 
    			return true; 
    	}
	}
	return false; 
}
public int orangesRotting(int[][] grid)
{
    // Code here
    // using bfs...
    Queue<Orange> queue = new LinkedList<>();
    // cal row and col
    int r = grid.length;
    int c = grid[0].length;
    
    // traverse through the 2D array and if rotten -->2
    // orange is present add timeframe,x,y
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            if(grid[i][j] == 2)
            {
                int x = i;
                int y = j;
            //    System.out.println("The 2 is"+x);
            //    System.out.println("The 2s y"+y);
                int timeframe = 0;
                Orange temp = new Orange(timeframe,x,y);
                queue.add(temp);
            }
        }
    }
    int ans = 0;
    while(!queue.isEmpty())
    {
        // take first element from queue
        Orange element = queue.peek();
     //   System.out.println("The elements x is"+ element.x);
     //   System.out.println("The elements y is"+ element.y);
        
                    // check for right adjacent
        if(isvalid(element.x,element.y+1,r,c) && grid[element.x][element.y+1] == 1)
        {
            grid[element.x][element.y+1] = 2;
           // System.out.println(element.x);
           // System.out.println(element.y+1);
            queue.add(new Orange(element.timeframe+1,element.x,element.y+1));
            
            
        }
        
        // check for left adjacent
        
        if(isvalid(element.x,element.y-1,r,c) && grid[element.x][element.y-1] == 1)
        {
            grid[element.x][element.y-1] = 2;
           // System.out.println(element.x);
           // System.out.println(element.y-1);
            queue.add(new Orange(element.timeframe+1,element.x,element.y-1));
        }
        
        // check for top adjacent
        
        if(isvalid(element.x-1,element.y,r,c) && grid[element.x-1][element.y] == 1)
        {
            grid[element.x-1][element.y] = 2;
           // System.out.println(element.x-1);
           // System.out.println(element.y);
            queue.add(new Orange(element.timeframe+1,element.x-1,element.y));
        }
        
        // check for down adjacent
        
        if(isvalid(element.x+1,element.y,r,c) && grid[element.x+1][element.y] == 1)
        {
            grid[element.x+1][element.y] = 2;
           // System.out.println(element.x+1);
           // System.out.println(element.y);
            queue.add(new Orange(element.timeframe+1,element.x+1,element.y));
        }
        

        
    
    
        
        ans = element.timeframe;
        queue.remove();
    }
    
    ans = checkall(grid,r,c)?-1:ans;
    
    return ans;
}

}

class Solution {
    public int orangesRotting(int[][] grid) {
    if(grid ==null || grid.length==0) return 0;
    int rows=grid.length;
    int cols=grid[0].length;
    Queue<int[]> queue=new LinkedList<>();
    int count_fresh=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j] == 2){
                   queue.offer(new int[]{i,j});
                }
                if(grid[i][j] !=0){
                    count_fresh++;
                }
            }
        }
        
        if(count_fresh==0){
            return 0;
        }
        
        int countMin=0, cnt=0;
        int dx[]={0,0, 1, -1}, dy[]={1, -1, 0 , 0};
        
        while(!queue.isEmpty()){
            int size=queue.size();
            cnt+=size;
            
            for(int i=0;i<size;i++){
                int[] point=queue.poll();
                for(int j=0;j<4;j++){
                    int x=point[0]+dx[j];
                    int y=point[1]+dy[j];
                    if(x<0 || y<0 || x>=rows || y>=cols || grid[x][y]==0 || grid[x][y]==2) continue;
                    
                    grid[x][y]=2;
                    queue.offer(new int[]{x,y});
                }
            }
            if(queue.size() !=0){
                countMin++;
            }
        } 
        return count_fresh==cnt ? countMin : -1;
    }
}

public int orangesRotting(int[][] grid)
{
int r=grid.length;
int c=grid[0].length;
int count=0;
int countFresh=0;
int[][] target=grid;
Queueq=new LinkedList<>();
for(int i=0;i<r;++i)
{
for(int j=0;j<c;++j)
{
if(target[i][j]==2)
{
q.add(new Pair(i,j));
}
if(target[i][j]==1)
{
countFresh++;
}
}
}
int[] x={-1,1,0,0};
int[] y={0,0,-1,1};
while(!q.isEmpty())
{
int size=q.size();
for(int i=0;i<size;++i)
{
Pair node=q.remove();
for(int p=0;p<4;++p)
{
int nx=x[p]+node.first;
int ny=y[p]+node.second;
if(nx>=0&&ny>=0&&nx<r&&ny<c&&target[nx][ny]==1)
{
countFresh--;
target[nx][ny]=2;
q.add(new Pair(nx,ny));
}
}
}
if(q.size()!=0)
{
count++;
}
}

    return countFresh==0?count:-1;
}

}