Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Rotting Oranges

Medium
graphbfsmatrix

In a grid, 0 is empty, 1 is a fresh orange, 2 is rotten. Every minute, fresh oranges 4-adjacent to a rotten one rot. Return the minutes until no fresh orange remains, or -1 if that never happens.

Input

  • Line 1: r c
  • Next r lines: the grid rows

Output: minutes, or -1.

Example 1
Input:
3 3
2 1 1
1 1 0
0 1 1
Output:
4
Example 2
Input:
3 3
2 1 1
0 1 1
1 0 1
Output:
-1

The bottom-left orange is unreachable.

Example 3
Input:
1 3
0 2 0
Output:
0

Constraints

  • 1 ≤ r, c ≤ 10
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.