Задача №1917. Клетчатые фигурки
Рассмотрим прямоугольное клетчатое поле из N строк и M столбцов, в котором некоторые клетки закрашены. Соседними назовём клетки, имеющие общую точку. Путём назовём последовательность закрашенных соседних клеток длины больше, чем 1. В этой задаче вам нужно на данном поле найти количество замкнутых путей, имеющих форму квадратов и равнобедренных прямоугольных треугольников:
## ### #### ##### ###### ## # ### # # # #######
## # # # # # # # # # ## ## ## ## ## # #
### # # # # # # # ### # # # #
#### # # # # # # # # #
##### # # #### # ## ## # # # #
###### # # ## # # # # # ##
## # # # # ####### #
# # # ####### # #### #####
# # # # # # # # ###### #
# # # # # # # # #### ##### # # ##
# # # # # # ## # # # # # # # #
# # # # # # # ## # # # # # #
# # # # #### # ## ## # #
# ####### # # ######
Входные данные
В первой строке содержатся два целых числа \(N\) и \(M\) — размеры поля. В следующих \(N\) строках содержится по \(M\) символов «.» или «#», обозначающих пустые и закрашенные клетки, соответственно.
Выходные данные
Выведите единственное целое число — количество фигур.
Сдать: для сдачи задач необходимо войти в систему