АВТ
Язык:

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

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1221. Мозаика

Ограничение времени: 1 сек.
Ограничение памяти:131072 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил Igor Andrianov

Девочка Надя очень любит играть мозаикой, поэтому у неё есть множество различных вариантов мозаики. Как-то раз её младшая сестра высыпала несколько мозаик в одну кучку и как следует эту кучку перемешала, а так как отдельные элементы всех мозаик имеют одинаковый размер базового элемента (квадрат 1 × 1) и одинаковый цвет, то разделить элементы обратно стало невозможно.

Каждая мозаика укладывается в квадратную коробку с размером стороны N (2 ≤ N ≤ 5). Отдельный элемент мозаики состоит из квадратов 1 × 1, соединённых таким образом, что из любого квадрата элемента до любого другого его квадрата можно дойти, переходя через общие стороны квадратов, принадлежащих элементу. Количество квадратов в одном элементе не менее 1 и не более N 2. Кроме того, каждый элемент имеет такую форму и размеры, что взятый отдельно он помещается в пустую коробку из-под мозаики.

Надя берёт пустую коробку и выбирает K элементов (1 ≤ K ≤ N 2) таким образом, чтобы каждый из них подходил к данной коробке и, кроме того, суммарное количество квадратов у данных элементов равнялось ровно N 2. Теперь Наде остаётся лишь придумать вариант укладки элементов в коробку или понять, что это невозможно. В первом случае выбранные элементы можно считать единой мозаикой, а во втором — следует выбрать другие элементы.

Вам требуется помочь Наде уложить выбранные элементы в коробку. Элементы при укладывании разрешается двигать, вращать на угол кратный 90 градусам и переворачивать на другую сторону.

Формат входных и выходных данных

Первая строка входных данных содержит числа N и K, разделённые пробелом. В последующих строках следуют описания K элементов мозаики. Описания отдельных элементов разделены пустой строкой.

Каждый элемент представлен уложенным произвольным образом в коробку из-под мозаики. Описание элемента представляет собой N строк по N символов в каждой. Символ '.' (точка) соответствует пустой клетке коробки, а символ '*' (звёздочка) — клетке элемента.

Выходные данные должны содержать описание любой допустимой укладки элементов в коробку или число 0, если укладка невозможна. Описание укладки представляет собой N строк по N разделённых пробелами чисел в каждой. Каждое число описывает номер элемента, который занимает соответствующую клетку коробки. Элементы нумеруются в порядке следования во входных данных, начиная с 1.

Примеры

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

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

2 2

**

..

 

*.

*.

1 1

2 2

3 2

***

***

.*.

 

...

*..

*..

0

 

Условия всех задач XVI межвузовской олимпиады в одном файле


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Межвузовские олимпиады / XVI Межвузовская олимпиада 2013 /
1220. A - Факториал. 1221. 1222. C - Кондукторы 1223. D - Круги. 1224. E - Поезд
 
время генерации 0.14 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.