Problem Description

This problem is translated from CCO 2014 Day 1 T1 “Troyangles”.

Troy likes triangles, so he especially likes counting triangles. He has an $N \times N$ grid consisting of . and #. Help him count how many triangles made only of # appear in the grid. A triangle looks like this:

          #
    #    ###
#, ###, #####, ...

More formally, a triangle of height $h$ has $h$ rows, where $h$ is a positive integer. Row $i$ has $2i-1$ # characters $(1 \le i \le h)$. The rows are centered above each other, so the triangle is symmetric about its vertical center line.

Input Format

The first line contains an integer $N$, the size of the grid. The next $N$ lines each contain $N$ characters describing the grid.

Output Format

Output the number of triangles in the grid.

5
.....
.###.
.###.
#####
.....

16

Hint

For $20\%$ of the testdata, $1 \le N \le 50$.

For $100\%$ of the testdata, $1 \le N \le 2000$.

Translated by ChatGPT 5