Rotting Oranges - Python Solution

1. Introduction

The "Rotting Oranges" problem is an engaging challenge that involves a grid simulation, often used to teach breadth-first search (BFS) algorithms. The scenario involves rotting oranges in a grid where each rotten orange can infect adjacent fresh oranges. The task is to find the minimum time required for all oranges to become rotten or determine if it's impossible.

Problem

Given an m x n grid where each cell can be an empty cell (0), a fresh orange (1), or a rotten orange (2), every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. The goal is to return the minimum number of minutes that must elapse until no cell has a fresh orange. If it's impossible to rot all oranges, return -1.

2. Solution Steps

1. Use breadth-first search to simulate the rotting process of oranges.

2. Initialize a queue to keep track of rotten oranges and a counter for fresh oranges.

3. Add all initially rotten oranges to the queue.

4. Process the queue iteratively, rotting adjacent fresh oranges for each rotten orange.

5. After processing each level of the queue, increment a minute counter.

6. Continue until there are no more fresh oranges to rot or the queue is empty.

7. Check if any fresh oranges are left unrotted, indicating an impossible scenario.

8. Return the total minutes elapsed or -1 if it's impossible.

3. Code Program

from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    fresh = 0
    queue = deque()

    # Initialize queue with rotten oranges and count fresh oranges
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    directions = [(1,0), (-1,0), (0,1), (0,-1)]

    # BFS to rot adjacent oranges
    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if nx >= 0 and ny >= 0 and nx < rows and ny < cols and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh -= 1
                    queue.append((nx, ny))

    return minutes if fresh == 0 else -1

# Example Usage
print(orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))
print(orangesRotting([[2,1,1],[0,1,1],[1,0,1]]))

Output:

4
-1

Explanation:

1. Queue Initialization: The queue is initialized with positions of all initially rotten oranges, and fresh oranges are counted.

2. Breadth-First Search: The BFS iteratively processes each level of rotten oranges, spreading the rot to adjacent fresh oranges.

3. Time Counting: For each level processed in the queue (each minute), the time counter is incremented.

4. Rotting Process: Fresh oranges adjacent to rotten ones become rotten, reducing the count of fresh oranges.

5. Completion Check: If all fresh oranges become rotten, return the time elapsed. If some fresh oranges never rot, return -1.

6. Result: The function returns the minimum number of minutes until all oranges are rotten or -1 if it's impossible.