Rotten Oranges

Rotten Oranges

Given a grid of oranges, find the minimum time for all fresh oranges to rot, using multi-source BFS.

Input format

The first line contains R and C. The next R lines contain the grid (0=empty, 1=fresh, 2=rotten).

Output format

Print minutes until no fresh oranges remain, or -1 if impossible (4-directional).

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

1 11
2 2 1 2 2 0 1 2 1 1 2

1

7 7
0 0 1 0 1 1 1
0 0 2 1 2 1 0
1 1 1 1 0 2 2
2 2 1 0 0 0 0
1 0 2 0 2 1 0
0 0 2 2 2 2 1
2 2 2 1 0 2 0

3