P6143 [USACO20FEB] Equilateral Triangles P

Farmer John’s farm can be represented by an $N \times N$ grid ($1 \leq N \leq 300$). For each cell in the grid, if there is a cow in this cell, it is denoted by `*`; otherwise, it is denoted by `.`. FJ believes that the beauty of his farm is proportional to the number of triples of cows whose pairwise distances are equal. In other words, they form an equilateral triangle. Unfortunately, FJ only recently discovered that since his cows are all located at integer coordinate positions, it is impossible to have a beautiful triple of cows if we use Euclidean distance! So, FJ decided to switch to using “Manhattan” distance instead. Formally, the Manhattan distance between two points $(x_0,y_0)$ and $(x_1,y_1)$ is $|x_0-x_1|+|y_0-y_1|$. Given the grid describing the cow positions, compute the number of equilateral triangles.

The first line contains an integer $N$. The next $N$ lines each contain a string of length $N$. The $j$-th character of the $i$-th line indicates whether there is a cow at position $(i,j)$.

Output one integer, the required answer. It can be proven that the answer fits in a 32-bit signed integer type.

### Sample Explanation There are three cows, and they form an equilateral triangle because the Manhattan distance between every pair of cows is equal to two. ### Subtasks - For test cases $T$ ($T \in [2,11]$), $N=25T$. - For test cases $T$ ($T \in [12,15]$), $N=300$. Translated by ChatGPT 5