GraphMatrixBFSMulti-source BFS
In a grid, 0 is an empty cell, 1 is a fresh orange and 2 is a rotten orange. Every minute, each fresh orange that is next to (up, down, left or right) a rotten orange becomes rotten. Find the minimum number of minutes until no fresh orange remains, or -1 if that never happens.
Input
Line 1: r and c. Next r lines: c values each, 0, 1 or 2.
Output
Print the minimum number of minutes, or -1 if some fresh orange can never rot.
Constraints
1 <= r, c <= 20
Example 1
Input
3 3 2 1 1 1 1 0 0 1 1
Output
4
It takes 4 minutes for the last orange to rot.
Example 2
Input
3 3 2 1 1 0 1 1 1 0 1
Output
-1
The orange at the bottom-left is cut off.