# 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++) {

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;
}
```

Time Complexity: O(M*N).

Space Complexity: O(M*N).

where M = number of Rows in the matrix

N = number of Columns in the matrix