Jul 15, 2024

**Problem Statement**: Given a grid of dimensions`n x m`

where:`0`

: Empty cell`1`

: Fresh orange`2`

: Rotten orange

**Objective**: Determine the minimum time required to rot all oranges.**Rotting Mechanism**: Rotten oranges rot adjacent fresh oranges (up, down, left, right) in 1 unit of time.

**Example 1**:- Initial State: 2D grid with mixed fresh and rotten oranges.
- Time 1 Unit: Rotten oranges rot adjacent fresh oranges.
- Continue until all reachable fresh oranges are rotten or no fresh oranges left.
- Result: Time taken to rot all fresh oranges or
`-1`

if some fresh oranges can't be reached.

**Example 2**:- Multiple initially rotten oranges rot adjacent oranges in 1 unit of time.
- Check if all fresh oranges are rotten.

**Example 3**:- Single rotten orange in the grid.
- Follow similar rotting process as above.
- Return minimum time to rot or
`-1`

if any orange is unreachable.

- A rotten orange can only rot adjacent oranges (no diagonal rotting).
- If some oranges cannot be rotted (isolated by empty cells), return
`-1`

.

**Reason**: BFS processes nodes level-wise, ensuring minimum time traversal for rotting.**Why Not DFS**: DFS would take more steps/time as it goes deep into one branch before visiting others.**BFS Steps**:- Use a queue to traverse level by level.
- Initially, enqueue all rotten oranges with time
`0`

. - For each rotten orange, enqueue its adjacent fresh oranges with incremented time.
- Track the maximum time during the process.

**Initialization**:- Determine grid dimensions
`n`

and`m`

. - Create a queue to store rotten oranges and their rotting times.
- Create a visited array to mark rotten cells.

- Determine grid dimensions
**Enqueue Initial Rottens**:- Traverse grid and enqueue all initially rotten oranges with time
`0`

. - Mark these as visited.

- Traverse grid and enqueue all initially rotten oranges with time
**BFS Traversal**:- Dequeue elements and check their adjacent cells.
- Enqueue fresh oranges and update their rotting times.
- Mark these new rotten oranges as visited.

**Final Checks**:- Ensure all fresh oranges are rotten by checking the visited array.
- Return the total rotting time or
`-1`

if any fresh orange is left.

```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void rottenOranges(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
queue<pair<pair<int, int>, int>> q; // store cell position and time
vector<vector<int>> visited(n, vector<int>(m, 0));
int freshCount = 0; // fresh oranges count
// Enqueue initial rotten oranges
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 2) {
q.push({{i, j}, 0});
visited[i][j] = 1;
} else if (grid[i][j] == 1) {
++freshCount;
}
}
}
// Direction vectors for top, right, bottom, left
vector<int> dRow = {-1, 0, 1, 0};
vector<int> dCol = {0, 1, 0, -1};
int time = 0;
// BFS traversal
while (!q.empty()) {
auto cell = q.front(); q.pop();
int row = cell.first.first;
int col = cell.first.second;
int t = cell.second;
// Update the final time
time = max(time, t);
// Check all 4 possible neighbors
for (int i = 0; i < 4; ++i) {
int newRow = row + dRow[i];
int newCol = col + dCol[i];
// Check for valid cell and fresh orange
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m &&
grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
q.push({{newRow, newCol}, t + 1});
visited[newRow][newCol] = 1;
--freshCount;
}
}
}
// If there are still fresh oranges left
if (freshCount > 0) {
cout << "-1" << endl;
} else {
cout << time << endl;
}
}
int main() {
vector<vector<int>> grid = {{2,1,1},{1,1,0},{0,1,1}};
rottenOranges(grid);
return 0;
}
```

**Space Complexity**:`O(n * m)`

(queue and visited arrays).**Time Complexity**:`O(n * m)`

traversing each cell and its 4 neighbors.

- Use BFS for minimum time traversal in grid problems involving equal level processing.
- Ensure all fresh oranges are processed, otherwise return
`-1`

.