#P1950. Rectangle Cutting
Rectangle Cutting
Rectangle Cutting
Little Ming had an idea today: he wanted to cut out a rectangle from a used sheet of paper. The paper is of size $n \times m$ and is divided into $n \times m$ grid cells. Some cells already contain drawings (marked cells). When cutting, Ming can only cut along the grid lines, and the resulting rectangle must not contain any previously drawn (marked) cells. The rectangle can be of any size as long as it lies along the grid lines.
Determine the number of ways to cut out a rectangle (by choosing a subrectangle of the grid) that does not contain any pre-drawn cell.
inputFormat
The first line contains two integers $n$ and $m$, representing the number of rows and columns of the paper.
Each of the following $n$ lines contains a string of $m$ characters. Each character is either .
representing a free cell or *
representing a cell with a previous drawing. You can assume $1 \le n, m \leq$ (a reasonable upper limit).
outputFormat
Output a single integer: the number of ways to cut out a rectangle that does not include any pre-drawn cell.
sample
1 1
.
1