#5575. [Usaco2020 Feb]Equilateral Triangles

内存限制:512 MiB 时间限制:10 Sec

题目描述

FarmerJohn的牧场可以被表示为一个N×N的正方形方阵(1≤N≤300),包含1≤i,j≤N内的所有位置(i,j)。对于方阵内的每个方格,如果在这个位置上有一头奶牛,输入中对应的字符为'*',如果这个位置没有奶牛则为'.'。
FJ相信他的牧场的美丽程度正比于两两距离相等的奶牛三元组的数量。也就是说,她们组成一个等边三角形。不幸的是,直到最近FJ才发现,由于他的奶牛都处在整数坐标位置,如果使用欧几里得距离进行计算,不可能存在美丽的奶牛三元组!于是,FJ决定改用“曼哈顿”距离。形式化地说,两点(x0,y0)和(x1,y1)之间的曼哈顿距离等于|x0−x1|+|y0−y1|
给定表示奶牛位置的方阵,计算等边三角形的数量。

输入格式

第一行包含一个整数。
对于每个1≤i≤N,第i+1行包含一个长为N的仅由字符'*'和'.'组成的字符串。第j个字符描述了是否在位置(i,j)存在一头奶牛。

输出格式

输出一个整数,为所求的答案。可以证明答案可以用32位有符号整数型存储。

样例

样例输入


			
3
*..
.*.
*..

样例输出


			
1
有三头奶牛,并且她们组成了一个等边三角形,因为每对奶牛之间的曼哈顿距离都等于二。

数据范围与提示