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; }
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
Submitted by Saurabh Tyagi (styagi689)
Download packets of source code on Coders Packet
Comments