A lump of butter is placed on an R x C (5 <= R, C <= 100) grid as shown in fig 1 below. R is the number of rows and C is the number of columns.
The butter melts if exposed to air at room temperature. If two sides of a square of butter are exposed to the air, then that square melts and disappears in one hour. All the squares marked M below will disappear after one hour.
After four hours, the entire block will disappear. (Work it out.)
If there are holes in the block of butter (see fig 2.), then these are assumed not to be heated by the outside air and therefore squares touching the holes do not melt.
In one hour, when these squares have disappeared (resulting in fig 3), the warm air flows into these regions, so in the next hour, the squares marked M in fig 3 will disappear.
The border squares of the grid will not contain any butter.
Write a program that calculates the time in hours after which the butter will have melted down and completely disappeared.
The first line has two integers, R and C (5 <= R, C <= 100). The next R lines contain the grid; a 1 represents a square with butter on it and a zero represents a square with no butter on it.
The output is one integer, the number of hours which it takes the butter to melt.
8 9 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4