Rotting Oranges :
Difficulty Level : Easy
Submissions : 134
Asked In :
Marks :10
: 2 | : 0
You are given an n x m grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Input
The first line contains N (1 <= N <= 1e4) and M (1 <= M <= 1e4) , the size of the grid.
Next N lines contain M integers, 0 1 or 2, representing the grid.
N*M <= 1e4 for all test cases
Output
Output a single integer, the minimum number of minutes.
Examples
Input
3 3 2 1 1 1 1 0 0 1 1
Output
4
Input
3 3 2 1 1 0 1 1 1 0 1
Output
-1
