P4813 [CCO 2014] Troy and Triangles

**This problem is translated from [CCO 2014](https://cemc.math.uwaterloo.ca/contests/computing/2014/index.html) Day 1 T1 “[Troyangles](https://cemc.math.uwaterloo.ca/contests/computing/2014/Stage%202/day1.pdf)”.** 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: ```plain # # ### #, ###, #####, ... ``` 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.

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

Output the number of triangles in the grid.

For $20\%$ of the testdata, $1 \le N \le 50$. For $100\%$ of the testdata, $1 \le N \le 2000$. Translated by ChatGPT 5