Pavementland Flash Flood Forecast

Pavementland is a rectangular city modeled as a grid of size $$h \times w$$. The rows are numbered from 1 to $$h$$ from north to south, and columns are numbered from 1 to $$w$$ from west to east. The cell in row $$r$$ and column $$c$$ is denoted as \((r, c)\).

Each cell is either empty or contains a building, and there is at least one empty cell. Due to a monsoon surge, flash floods occur as follows:

• Initially, one empty cell is flooded with water.
• An empty cell adjacent (sharing an edge) to a flooded cell becomes flooded.
• A cell containing a building becomes flooded (i.e. the building collapses) if it is adjacent to at least two flooded cells.

Water cannot flow outside the grid. Let $$f((r, c))$$ be the total number of cells that become flooded (including collapsed buildings) when the initial flood starts at the empty cell \((r, c)\). City officials want to know the sum of $$f((r, c))$$ over all empty cells \((r, c)\).

Note: Two cells are adjacent if they share a common edge. Each cell has at most four adjacent cells.

inputFormat

The first line contains two integers $$h$$ and $$w$$, representing the number of rows and columns of the grid.

The following $$h$$ lines each contain a string of length $$w$$. Each character is either a . representing an empty cell or a # representing a building. It is guaranteed that at least one cell is empty.

outputFormat

Output a single integer — the sum of $$f((r, c))$$ over all empty cells \((r, c)\).

sample

2 2
..
.#

9