409964: GYM103870 I Counting Flags

Timothy is the president of the triangle fan club, and they have decided to create a flag! The design they settled on was an isosceles right triangle. They want to cut it out from a $$$N \times M$$$ rectangular piece of cloth with the two legs of the triangle being parallel to the sides of the cloth. The orientation of the flag matters, one leg of the triangle must be on the bottom and the other must be on the right (more details are given in the notes).

Unfortunately, the cloth had been stored in the attic with moths, so there were holes all over it. Timothy wants to know how many places still exists on the cloth that he can a flag out of.

Timothy hasn't decided on the size of the flag yet, and he wants to explore all the possibilities. He asks you to find the number of different places he can cut a flag out of for each flag size from $$$2$$$ to $$$\min{(N, M)}$$$. A flag of size $$$X$$$ has legs of length $$$X$$$ each.

The first line contains $$$2$$$ integers, $$$N$$$ and $$$M$$$ $$$(1 \leq N, M \leq 1000)$$$, the number of rows and number of columns of the cloth.

The next $$$N$$$ lines contain $$$M$$$ characters each. The characters are either $$$.$$$ or $$$*$$$, with $$$.$$$ representing a hole in the cloth and $$$*$$$ representing that there isn't.

Print $$$\min{(N, M)} - 1$$$ lines. The $$$i$$$th line denotes the number of different spots Timothy is able to cut a flag of size $$$i + 1$$$ out of.

4 5
..*.*
*****
*****
*****

10
5
1

A valid flag of size $$$3$$$ looks like this: $$$$$$ \begin{matrix} . & . & *\\ . & * & *\\ * & * & * \end{matrix} $$$$$$ Other orientations of flags don't work, for example: $$$$$$ \begin{matrix} * & . & .\\ * & * & .\\ * & * & * \end{matrix} $$$$$$ is not a valid flag of size $$$3$$$.

Two flags are considered to be in different locations if they have any point that is different between them. They are allowed to overlap.

$$$---------------------------------$$$

Idea: Timothy

Preparation: Mantlemoose, Timothy

Occurrences: Novice 10, Intermediate 7