Table of Content

Rotten Oranges Problem

Introduction:

• The Rotten Oranges problem is a grid-based problem where each cell can contain one of three values:
  • 0: an empty cell.
  • 1: a fresh orange.
  • 2: a rotten orange.
• The problem simulates how the rot spreads from rotten oranges to adjacent fresh ones every minute. The goal is to determine the minimum time required to rot all fresh oranges or return 1 if it's impossible for all to rot.

Approach:

• Graph Representation: Treat the grid as a graph where each cell is a node, and edges exist between adjacent cells (up, down, left, right).
• BFS (Breadth-First Search): BFS is ideal for this problem because it explores the grid level by level, simulating the minute-by-minute spread of rot.
• Steps:
  1. Initialization: Start by identifying all rotten oranges in the grid and enqueue them with a timestamp of 0 minutes.
  2. BFS Execution: For each rotten orange, spread the rot to adjacent fresh oranges, marking them as rotten and enqueuing them with an incremented timestamp.
  3. Final Check: After BFS completes, if any fresh oranges remain unrotted, return 1. Otherwise, return the maximum timestamp recorded, which represents the total time taken.

Example:

• A grid is walked through step-by-step using BFS, showing how oranges rot over time.
• A scenario is also provided where some fresh oranges remain unrotted due to being isolated by empty cells, leading to a return value of 1.

Applications and Learning Points:

• This problem is an excellent practical application of BFS and is often used to teach the concepts of grid traversal, graph theory, and real-world problem modeling using algorithms.

Dijkstra’s Algorithm

Introduction:

• Dijkstra’s Algorithm is used to find the shortest path from a single source node to all other nodes in a graph with non-negative weights.
• It's widely used in network routing and navigation systems to find the most efficient path.