Покрытие

Представим себе комнату размера m×n, пол которой расчерчен линиями сетки на квадраты 1×1. Предлагается покрыть пол этой комнаты дощечками весьма необычного вида.

Одна дощечка представляет собой фигуру, состоящую ровно из 6 клеток квадрата 3×3 и являющуюся связной по стороне (иными словами, из любой клетки можно попасть в любую другую, перемещаясь между центрами соседних клеток только по вертикали и горизонтали и не покидая пределов фигуры). Все дощечки одинаковы. Дощечки выкладываются на пол так, чтобы стороны их клеток совмещались с линиями сетки на полу; их нельзя ни поворачивать, ни перевернуть и положить обратной стороной вверх.

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

Требуется узнать, какое минимальное количество дощечек данного вида потребуется, чтобы построить покрытие пола нашей комнаты.

Входные данные

В первой строке входного файла INPUT.TXT заданы через пробел два целых числа m и n (1 ≤ m, n ≤ 9). В следующих трех строках описан квадрат 3×3, содержащий дощечку. Каждая из этих строк содержит ровно три символа. Символ «X» (икс большое) соответствует клетке дощечки, а символ «.» (точка) – пустой клетке. Гарантируется, что эти строки не содержат других символов, суммарное количество символов «X» на них равно шести, и фигура из букв «X» связна по стороне.

Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество дощечек данного вида, которые нам потребуются, чтобы построить покрытие пола.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]