Minimum time required so that all tomatoes are rotten in C++

To determine the minimum time required so that all the tomatoes become rotten, and understanding the application of BFS in this scenario using C++.

We are given an M x N matrix where each cell can have one of three values:
a) 0 representing an empty cell,
b) 1 representing a fresh tomato, or
c) 2 representing a rotten tomato.

A rotten tomato at any index [x,y] can rot the other fresh tomatoes at indexes up [x-1,y], down [x+1,y], left [x,y-1] and right [x,y+1].Determine the minimum time required so that all the tomatoes become rotten, if it is impossible to rot every tomato then just return -1.

SOLUTION:

The efficient way is to use the Breadth-First Search(BFS) algorithm and the Queue data structure. As the fresh tomatoes are rotten when they are in contact with other rotten tomatoes. The idea is similar to the BFS on a graph where we need to start the search from inner/closer layers to the outer/farther layers.

Let's dive into the implementation for better understanding.

CODE:

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

int tomatoesRot(vector& grid) {
    //number of valid cells (cells with some tomato)
    int ct = 0;
    //result
    int res = -1;
    //actually queue of pairs of coord i and j
    queue q;
    
    //ways to move
    vector dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    //create staring nodes to queue to do bfs
    for(int i = 0; i < grid.size(); i++) {
        for(int j = 0; j < grid[0].size(); j++) {
            //increasing number of valid cells
            if(grid[i][j] > 0) 
                ct++;
            
            //only rotten tomatoes must be on initial step of queue
            if(grid[i][j] == 2) 
                q.push({i, j});
        }
    }
    
    //BFS
    while(!q.empty()) {
        
        //we do one step from rotten
        res++;
        
        //see next comment
        int size = q.size();
        
        //need to start from all rotten nodes at one moment 
        for(int k = 0; k < size; k++) {
            
            //take node from head
            vector cur = q.front();
            q.pop();
            
            //number of valid decreasing
            ct--;
            
            //need to look through all four directions
            for(int i = 0; i < 4; i++) {
                //taking coords
                int x = cur[0] + dir[i][0];
                int y = cur[1] + dir[i][1];
                
                //if we go out of border or find non-fresh tomato, we skip this iteration
                if(x >= grid.size() || x < 0 || y >= grid[0].size() || y < 0 || grid[x][y] != 1) 
                    continue;
                
                //tomato becomes rotten
                grid[x][y] = 2;
                
                //this tomatoe will make neighbour tomato rotten
                q.push({x, y});
            }
        }
    }
    //if we looked through all tomatoes, return result, else -1
    return (ct == 0) ? max(0, res) : -1;
}

int main()
{
 
    vector grid { { 1, 1, 0, 0, 2 },
                    { 1, 2, 1, 2, 2 },
                    { 1, 2, 0, 1, 1 } };
 
    cout << "Max time required for rotting all tomatoes: " << tomatoesRot(grid);
 
    return 0;
}

Coders Packet

Minimum time required so that all tomatoes are rotten in C++

Comments