Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Покрытие

(Время: 2 сек. Память: 32 Мб Сложность: 74%)

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

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13 3
.X.
XXX
XX.
3
23 2
XXX
XXX
...
1
32 3
XXX
XXX
...
2
42 2
XXX
X.X
..X
2

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

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

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru