| Codeforces Round 249 (Div. 2) |
|---|
| Закончено |
Задана сетка размера n × m, некоторые узлы которой черные, а остальные белые. Более того, сетка не совсем обычная — в каждом единичном квадрате сетки проведены диагонали.
На рисунке ниже изображен пример такой сетки размера 3 × 5. Четыре узла этой сетки черные, остальные 11 узлов белые.
Требуется посчитать количество таких треугольников на заданной сетке, что:
- их углы совпадают с белыми узлами, а площадь ненулевая;
- все стороны проходят по линиям сетки (горизонтальным, вертикальным или диагональным);
- никакая сторона не содержит черных узлов.
В первой строке записаны два целых числа n и m (2 ≤ n, m ≤ 400). В каждой следующих n строк содержится по m символов (нулей и единиц) — описание сетки. Если j-й символ в i-й строке равен нулю, значит узел на i-й горизонтальной линии и на j-й вертикальной линии покрашен в белый цвет. Иначе этот символ покрашен в черный цвет.
Горизонтальные линии нумеруются от единицы сверху вниз, вертикальные линии нумеруются от единицы слева направо.
Выведите единственное целое число — количество требуемых треугольников.
3 5
10000
10010
00001
20
2 2
00
00
4
2 2
11
11
0
На рисунке ниже красным и синим цветами выделены треугольники, которые считаются в ответе (это не все требуемые треугольники, а только два из них). Зеленым выделен один из неподходящих треугольников. Он не подходит, поскольку не все его стороны проходят по линиям сетки.
