Rotten Oranges (Breadth-First Search)

Welcome to our in-depth guide on the Rotten Oranges Problem solved using Breadth-First Search (BFS) algorithm! 🎯

This tutorial is designed for beginners and intermediate learners alike, and we'll cover the problem from the ground up, explaining not just how to solve it, but also why the approach works. Let's dive in! 📝

What is Breadth-First Search (BFS)?

BFS is a popular algorithm used for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node in graph) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. 💡

The Rotten Oranges Problem

The Rotten Oranges problem is an interesting and practical problem that involves determining the minimum number of days needed to make all oranges in a grid fresh again. The grid represents an orchard where each cell can contain one of three values: 0 (fresh orange), 1 (rotten orange), or 2 (unused cell). 🍊

Problem Statement

In a given grid, if a fresh orange is adjacent to a rotten orange, it will become rotten in 24 hours. When a cell with a rotten orange is explored, we mark it as visited and add its adjacent fresh oranges to the queue to be explored in the next day. The goal is to find the minimum number of days required to rot all the oranges in the grid or, if it's impossible, determine that no number of days will suffice. ✅

Solving the Rotten Oranges Problem with BFS

Let's dive into the solution using Python:

python

def rotten_oranges(grid):
    rows = len(grid)
    cols = len(grid[0])
    queue = deque()

    def is_valid(r, c):
        return 0 <= r < rows and 0 <= c < cols

    def add_to_queue(r, c):
        if not grid[r][c] or grid[r][c] == 2:
            return
        grid[r][c] = 2
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if is_valid(r + dr, c + dc) and grid[r + dr][c + dc] == 1:
                queue.append((r + dr, c + dc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                add_to_queue(r, c)

    days = 0
    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                if is_valid(r + dr, c + dc) and grid[r + dr][c + dc] == 1:
                    add_to_queue(r + dr, c + dc)
                    grid[r + dr][c + dc] = 2
        days += 1

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                return -1
    return days

Let's go through the function:

Define the helper functions is_valid and add_to_queue to check if a cell is within the grid boundaries and to add the adjacent fresh oranges to the queue, respectively.
Initialize the BFS with the rotten oranges found in the input grid.
In the main BFS loop, dequeue a rotten orange, mark it as visited, and explore its fresh neighbor oranges.
If all fresh oranges have been rot, return the number of days needed. If some fresh oranges remain unrot after the BFS ends, return -1.

Putting it into Practice 💡

Now that we've explored the Rotten Oranges problem and its solution using BFS, let's practice with an example:

Example:

Given the following grid:

Using the provided function, the rotten oranges would take 4 days to spread the rot throughout the entire grid:

Quiz Time 🎯

Question: What does the BFS algorithm do in the Rotten Oranges problem?

It starts at a random point in the grid and explores all cells within a fixed number of moves
It explores the entire grid at once, marking all oranges as rotten
It starts at the root of the grid and explores all neighbor cells at the current depth before moving on to the next level
It marks all fresh oranges as rotten in a single pass

Correct: It starts at the root of the grid and explores all neighbor cells at the current depth before moving on to the next level.

Explanation: The BFS algorithm is used to traverse the grid and rot the oranges systematically, exploring all neighbor cells at the current depth before moving on to the next level. This ensures that the rot spreads optimally throughout the grid.