Дистанционный практикум по программированию

Классы 7-8. Задача 2 - "Клингонские боевые бублики"

Петя и Вася - поклонники вселенной Star Trek. Петя любит рисовать на клетчатой бумаге фигурки фантастических боевых космических кораблей нации Клингонов из Star Trek - "клингонские боевые бублики". На клетчатой бумаге они представляются группой закрашенных ячеек 3 x 3 с пустой клеткой в центре:

XXX
X.X
XXX

Пока Вася ходил за печеньем, Петя взял клетчатую бумагу и стал рисовать эти корабли на бумаге. Когда Вася вернулся, он посмотрел на схему кораблей Пети и задумался - какое максимальное количество клингонских боевых бубликов мог нарисовать Петя. Вася знает, что корабли могут касаться друг друга и границ поля, могут даже пересекаться друг с другом, но не могут совпадать полностью.

Исходные данные

В первой строке входных данных записаны через пробел целые числа N и M - количество строк и столбцов на бумаге. 3 <= N,M <= 15.

В следующих N строках из M символов каждая задано поле, на котором размещены корабли. Заполненная клетка обозначается символом ’X’ (заглавная латинская икс), а пустая - ’.’ (точка).

Гарантируется, что поле было получено корректным размещением кораблей.

Результат

В единственной строке выведите максимальное количество кораблей, которое могло быть расположено на поле.

Пример

4 4
XXX.
XXX.
XXX.
XXX.

2

4 4
XXX.
X.X.
XXX.
....

1