P4813 [CCO 2014] Troy 与三角形

题目描述

本题译自 CCO 2014 Day1 T1「Troyangles」

Troy 喜欢三角形，所以他也特别喜欢数三角形。他有一个由 . 和 # 组成的 $N\times N$ 的网格。帮他数数在网格中仅由 # 组成的三角的个数。三角形表示为如下形式：

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

更加形式化地说，一个高度为 $h$，有 $h$ 列的三角形，其中 $h$ 为正整数，第 $i$ 行有 $2i-1(1\le i \le h)$ 个 #，行在彼此上方居中，所以它们是关于它们的垂直中线对称的。

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

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

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

对于 $20\%$ 的数据，$1\le N\le 50$；

对于 $100\%$ 的数据，$1\le N \le 2000$。