Rotten Oranges Problem

Introduction

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.

Problem Breakdown

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.

Important Observations

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

Algorithm Choice: BFS (Breadth-First Search)

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.

BFS Implementation

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.
Enqueue Initial Rottens:
- Traverse grid and enqueue all initially rotten oranges with time 0.
- Mark these as visited.
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;
}

Complexity Analysis

Space Complexity: O(n * m) (queue and visited arrays).
Time Complexity: O(n * m) traversing each cell and its 4 neighbors.

Conclusion

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