Minimum Time to Rot All Oranges in a Grid

You are given an R x C grid where each cell contains 0 (empty), 1 (a fresh orange), or 2 (a rotten orange). Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange also becomes rotten. Determine the minimum number of minutes that must pass until no fresh orange remains anywhere in the grid. If some fresh orange can never become rotten, print -1.

Input: The first line contains R and C. Each of the next R lines contains C integers (0, 1, or 2) describing one grid row. Output: Print a single integer: the minimum number of minutes for every fresh orange to rot, or -1 if that is impossible.

1 <= R, C <= 200; grid values are 0, 1, or 2

This is a canonical example of 'multi-source BFS' - a technique that generalizes single-source BFS by starting from SEVERAL points at once, useful whenever a process spreads simultaneously from multiple origins rather than just one.

Given a grid of fresh and rotten oranges, find the minimum time until every reachable fresh orange has rotted, spreading from all rotten oranges at once. Brute force: Simulate the spread minute by minute using nested loops over the whole grid repeatedly, checking every cell each minute for a newly-adjacent rotten neighbor - this works but re-scans the ENTIRE grid every minute, costing far more than a queue-driven approach that only touches cells actually undergoing a state change. Optimised: A MULTI-SOURCE BFS (seeding the queue with ALL rotten oranges at once, rather than running separate single-source BFS from each) naturally processes the grid level by level, where each 'level' corresponds to exactly one minute - this guarantees every fresh orange's rot-time is found in the minimum number of steps, with each cell visited only once.

1. Seed a queue with the POSITIONS of EVERY rotten orange at once (a multi-source BFS), not just one starting point. 2. Process the queue one full minute (one full BFS level) at a time - everything currently in the queue rots its adjacent fresh oranges SIMULTANEOUSLY, and those newly-rotted oranges get enqueued for the NEXT minute. 3. After the BFS finishes, if any fresh orange is still left unrotted, it was never reachable - print -1; otherwise, the number of minutes elapsed is the answer.

Time: O(R * C) - every cell is enqueued and processed at most once. Space: O(R * C), for the BFS queue in the worst case (a grid entirely of rotten oranges initially).

A grid with no fresh oranges at all requires 0 minutes; a fresh orange with no rotten orange ever adjacent to it (directly or through a chain of fresh oranges) makes the answer -1.

Be ready to explain WHY seeding the queue with ALL rotten oranges simultaneously (rather than picking just one and running separate searches) is essential - this multi-source technique is what correctly models oranges rotting from MULTIPLE spreading fronts at the same time.