Sandcastle
InterviewTime limit1sMemory limit256 MB
Each wave washes away every sand cell whose empty count among its eight neighbors reaches its firmness, so count the waves until no cell collapses.
- Level
Medium5 of 10
- Topics
- BFS, Simulation, Matrix
- Solved
- No attempts yet
Problem
Myungwoo went to the sea with his friends for the summer holiday. The beach they picked is called ALPS. Wonchul keeps looking at the people in swimsuits, but Myungwoo cares about the sand instead. Sand can be shaped into anything, and a sand figure washed away by a wave looks like it knows its brightest moment and chooses to vanish on its own. Nobody agreed with him, so Myungwoo built a sandcastle by himself.
Myungwoo built the castle knowing that waves would knock it down one day. The castle sits on a two dimensional grid, and every cell has its own firmness. Firmness is a digit from 1 to 9.
When one wave comes in, each cell looks at its 8 surrounding cells (up, down, left, right and the four diagonals). If the number of those cells that hold no sandcastle is greater than or equal to the firmness of the cell, the cell collapses. In every other case the cell survives the wave. The cells that collapse in one wave are decided together from the state right before that wave, and they collapse at the same time. A collapsed cell holds no sandcastle from then on.
If waves keep coming, the shape of the sandcastle stops changing at some point. Find how many waves have to come in before the shape stops changing.
Input
The first line contains the height and the width of the grid. ()
Each of the next lines contains characters that describe the sandcastle. Each character is a digit from 1 to 9 or '.'. A digit is the firmness of the sand in that cell, and '.' means that the cell holds no sandcastle.
The sandcastle does not touch the border of the grid.
Output
Print on the first line how many waves have to come in before the shape of the sandcastle stops changing. If the shape never changes, print 0.
Explanation
Look at the sandcastle below.
......
.939..
.3428.
.9393.
......
The first wave turns it into this.
......
.9.9..
..428.
.9.9..
......
The first wave leaves two more empty cells around the 2, so the next wave washes that 2 away.
......
.9.9..
..4.8.
.9.9..
......
The wave after that washes away the 4 in the middle.
......
.9.9..
....8.
.9.9..
......
From now on the sandcastle keeps this shape no matter how many waves come in. Three waves are needed before the shape stops changing.