The Rot Spreads

Difficulty: 1600 4000 ms 128 MB

bfs graphs

Crates hold fresh apples (F), rotten apples (R) or are empty (E). Each minute, rot spreads to side-adjacent fresh apples. Print the minutes until nothing fresh remains, or −1 if some apples never rot.

Input: the first line has N and M; the next N lines each have M characters.

Output: the number of minutes, or −1 (0 if there is nothing fresh).

Constraints:

• 1 ≤ N, M ≤ 500

Sample Tests

3 3
RFF
FFF
EFF

4

1 3
FER

-1

Read the Editorial Statistics