Cheese
Time limit1sMemory limit128 MB
Simulate hourly melting of cheese cells on a grid, where a cell melts if at least two sides touch outside air reachable via BFS/flood fill, and output total hours until all cheese disappears.
- Level
Medium6 of 10
- Topics
- BFS, Simulation, Matrix
- Solved
- No attempts yet
Problem
A very thin piece of cheese is placed on an N×M grid. N is the number of rows, and M is the number of columns. When the cheese is left at room temperature, parts touching air slowly melt. A cheese cell disappears exactly 1 hour later if at least two of its four sides are touching outside air. Therefore, in Figure 1, every cheese cell marked C disappears after 1 hour.
Figure 1
An empty space trapped inside the cheese is not considered connected to outside air. Thus, in Figure 2, cheese cells touching only the trapped space do not melt, and only the cells marked C disappear. After some time, if that trapped space becomes connected to the outside, it also becomes outside air, and the newly exposed cells marked C disappear as in Figure 3.
Figure 2
Figure 3
No cheese is placed on the outer border of the grid. Compute the exact number of hours required for all given cheese to melt.
Input
The first line contains two integers N and M, the size of the grid. (5 ≤ N, M ≤ 100)
Each of the next N lines describes one row of the grid. A cell containing cheese is written as 1, and an empty cell is written as 0. The values are separated by spaces.
Output
Print one integer: the exact number of hours required for all given cheese to melt.