Loading...
Loading...
Loading...
A hostel mess stores oranges in a crate shaped like a grid. Each cell is empty, holds a fresh orange or holds a rotten orange.
Every minute, each rotten orange makes the fresh oranges right above, below, left and right of it rotten too. Oranges do not spread rot diagonally, and rot cannot cross an empty cell.
Print the number of minutes until no fresh orange is left. If some fresh orange can never become rotten, print -1. If there are no fresh oranges at the start, print 0.
. is an empty cell, F is a fresh orange and R is a rotten orange.., F or RExample 1
Input
3 3 RFF FF. .FF
Output
4
Minute 1 rots two oranges, minute 2 two more, minute 3 the middle of the last row and minute 4 the last corner. The answer is 4.
Example 2
Input
3 3 RFF .FF F.F
Output
-1
The orange in the bottom-left corner has empty cells on both sides, so rot never reaches it.
Try the problem first. Open one hint at a time.
Think of the rot moving in rounds: all oranges that rot in minute 1, then all that rot in minute 2, and so on.
Put every rotten orange into one queue at the start, not just one of them. They all spread at the same time.
Process the queue one level at a time: take exactly the cells that were in the queue when the minute started, and add the newly rotten ones for the next minute.
Count the fresh oranges at the start and lower the count each time one rots. Stop when the count reaches 0, and print -1 if the queue runs out first.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor