Задача №3857. Головоломка
Картина в голове Штирлица не складывалась. За год из Центра поступило N · M фрагментов нового задания. Штирлиц запомнил каждый фрагмент и теперь складывает из них целое сообщение.
Текст задания записан на клетчатой прямоугольной странице размера (5N) × (5M), который разрезан на N · M частей. Каждый фрагмент сообщения можно представить квадратом 5 × 5 (серые клетки), у которого с каждого краю (заштрихованные области) может быть только один «выступ» или «впадина». Обратите внимание, что к краям не относятся углы квадрата (см. иллюстрацию).
Более формально, каждый фрагмент можно представить в виде фигуры, которая получена из левой части иллюстрации, изменением цвета не более чем одной клетки из каждой заштрихованной области.
Фрагмент может иметь ровную сторону (т.е. не имеет выступа или впадины) только если соответствующая сторона фрагмента является границей сообщения.
Требуется написать программу, которая поможет Штирлицу собрать из фрагментов целое сообщение.
В первой строке входных данных даются размеры сообщения — натуральные числа N и M (1 ≤ N ≤ 5, 1 ≤ M ≤ 4).
В следующих 7 · N · M строках по 7 символов задаются фрагменты сообщения. Каждый фрагмент состоит из 7 строк. Пустая часть фрагмента задается символами «.», а часть фрагмента, содержащая текст, символами «#».
Выведите 7 · N строк по 7 · M символов, задающих как надо разложить части, чтобы получить целое сообщение. Части сообщения можно совмещать только параллельным переносом (то есть, запрещается поворачивать и переворачивать фрагменты сообщения).
Если существует несколько способов восстановить сообщение, требуется вывести любой из них. Решения, корректно работающие при ограничениях N · M ≤ 10, оцениваются в 50 баллов.
1 2 ....... .#####. .#####. .####.. .#####. .#####. ....... ....... .#####. .#####. ######. .#####. .#####. .......
.............. .#####..#####. .#####..#####. .####..######. .#####..#####. .#####..#####. ..............