Flooded Important Regions

After a sudden flood, oibh headquarters has been partly submerged. Fortunately, walls (represented by *) have been built at some key locations. An important region within the headquarters is represented by a 0. However, if an important region is completely enclosed by walls, the flood water cannot enter that area.

Given a grid representing the wall layout of oibh headquarters, your task is to determine how many important regions (0) have not been flooded.

The flood water starts from the outside of the grid (i.e. from any cell on the border that is not a wall) and flows to adjacent cells in the four cardinal directions (up, down, left, right), but cannot pass through walls. An important region is considered safe if it is not reached by the water.

The approach is to perform a flood-fill from all non-wall border cells and count the 0 cells that remain unvisited.

Note: In any formulas, use LaTeX format, e.g., $\text{safe count} = \#\{\text{cell } (i,j) \mid grid[i][j]=='0' \text{ and not flooded}\}$.

inputFormat

The first line contains two integers m and n representing the number of rows and columns of the grid.

The next m lines each contain a string of length n. The characters in the grid can be:

• * representing a wall, which water cannot pass.
• 0 representing an important region.
• . representing an empty area.

Water starts from any border cell that is not a wall and flows to adjacent cells in the four directions.

outputFormat

Output a single integer: the number of important regions (cells containing 0) that are not flooded.

sample

3 3
***
*0*
***

1