Классы 7-8. Задача 2 - "Клингонские боевые бублики"
Петя и Вася - поклонники вселенной Star Trek. Петя любит рисовать на клетчатой бумаге фигурки фантастических боевых космических кораблей нации Клингонов из Star Trek - "клингонские боевые бублики". На клетчатой бумаге они представляются группой закрашенных ячеек 3 x 3 с пустой клеткой в центре:
XXX
X.X
XXX
Пока Вася ходил за печеньем, Петя взял клетчатую бумагу и стал рисовать эти корабли на бумаге. Когда Вася вернулся, он посмотрел на схему кораблей Пети и задумался - какое максимальное количество клингонских боевых бубликов мог нарисовать Петя. Вася знает, что корабли могут касаться друг друга и границ поля, могут даже пересекаться друг с другом, но не могут совпадать полностью.
Input
В первой строке входных данных записаны через пробел целые числа N и M - количество строк и столбцов на бумаге. 3 <= N,M <= 15.
В следующих N строках из M символов каждая задано поле, на котором размещены корабли. Заполненная клетка обозначается символом ’X’ (заглавная латинская икс), а пустая - ’.’ (точка).
Гарантируется, что поле было получено корректным размещением кораблей.
Output
В единственной строке выведите максимальное количество кораблей, которое могло быть расположено на поле.
Sample
| Input | Output |
|---|
4 4
XXX.
XXX.
XXX.
XXX.
|
2
|
4 4
XXX.
X.X.
XXX.
....
|
1
|
| 