Пастбище Фермера Джона может быть представлено \(N\times N\) квадратной
решёткой \((1\le N\le 300)\), состоящей из позиций \((i,j)\) для всех \(1\le i,j\le N\).
Для каждого квадрата решётки, соответствующий символ на вводе равен '*',
если в этой позиции находится корова (ровно одна) и '.' если нет коров в этой
позиции.
ФД считает, что красота пастбища прямо пропорциональна количеству таких троек коров,
что их позиции находятся на равных расстояниях друг от друга, другими словами
они образуют равносторонний треугольник. ФД считает расстояния не Евклидовые,
а Манхэттенские, т.е. расстояние между двумя позициями \((x_0,y_0)\) и \((x_1,y_1)\)
равно \(|x_0-x_1|+|y_0-y_1|\).
По заданной решётке, определяющей позиции коров, вычислите количество
равносторонних троек.
ОЦЕНИВАНИЕ:
будет 14 тестов с такими значениями \(N\in \{50,75,100,125,150,175,200,225,250,275,300,300,300,300\}.\)
ФОРМАТ ВВОДА (файл triangles.in):
Первая строка содержит одно целое число
\(N.\)
Для каждой из \(1\le i\le N,\) строка \(i+1\) ввода содержит строку длины \(N\),
состоящую только из символов '*' и '.'. \(j\)-ый символ описывает, существует корова
в позиции \((i,j)\) или нет
ФОРМАТ ВЫВОДА (файл triangles.out):
Выведите одно целое число, содержащее ответ. Можно доказать, что оно поместится
в 32-битное целое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
*..
.*.
*..
|
1
|