[CCO2014] Troy 与三角形

题目描述

**本题译自 [CCO 2014](https://cemc.math.uwaterloo.ca/contests/computing/2014/index.html) Day1 T1「[Troyangles](https://cemc.math.uwaterloo.ca/contests/computing/2014/Stage%202/day1.pdf)」** Troy 喜欢三角形,所以他也特别喜欢数三角形。他有一个由 `.` 和 `#` 组成的 $N\times N$ 的网格。帮他数数在网格中仅由 `#` 组成的三角的个数。三角形表示为如下形式: ```plain # # ### #, ###, #####, ... ``` 更加形式化地说,一个高度为 $h$,有 $h$ 列的三角形,其中 $h$ 为正整数,第 $i$ 行有 $2i-1(1\le i \le h)$ 个 `#`,行在彼此上方居中,所以它们是关于它们的垂直中线对称的。

输入输出格式

输入格式


第一行一个数 $N$ 表示网格大小,接下来 $N$ 行每行 $N$ 个字符表示这个网格。

输出格式


输出网格中的三角形个数。

输入输出样例

输入样例 #1

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

输出样例 #1

16

说明

对于 $20\%$ 的数据,$1\le N\le 50$; 对于 $100\%$ 的数据,$1\le N \le 2000$。