|
Задача - головоломка
Помогите решить задачу. Даже не знаю как подступиться.
Имеется головоломка из пяти кусочков, которые нужно составить в квадрат.
При составлении квадрата
1)кусочки нельзя вращать или изменять их ориентацию
2)нужно использовать все заданные кусочки.
----Задача-----
Написать программу, которая по заданным кусочкам определяет, как составить из них квадрат по вышеуказанным правилам, либо говорит, что для заданных кусочков это сделать невозможно
----Формат входных данных----
Исходный файл содержит несколько головоломок (т.е. наборов кусочков) для решения. В первой строке записано число кусочков n в головоломке. Далее идет n описаний кусочков в следующем формате: в отдельной строке записывается два целых числа – число строк и число столбцов в кусочке. Следующие строки описывают очертания кусочка, используя символы ‘0’ как обозначение пустого места и ‘1’.
Кусочки нужно нумеровать в порядке их появления, начиная с 1. Гарантируется, что все кусочки заданы корректно и их размеры не более 4 строки на 4 столбца.
Далее идет число кусочков в следующей головоломке, описания ее кусочков и т.д.
Файл заканчивается числом 0 в отдельной строке, которое не подлежит обработке.
----Формат выходных данных-----
Ваша программа должна выдать ответ в формате, показанном в примерах ниже. В выходной файл следует записать решение в виде квадрата из символов размером 4 строки на 4 столбца. Символы ‘1' представляют кусочек номер 1, символы ‘2’ – ку-сочек номер 2 и т.д. Для каждой головоломки решение должно быть отделено пустой строкой.
Если для заданных кусочков решения нет, то нужно записать строку NO SOLU-TION.
----Пример файла входных данных------
4
2 3
111
101
4 2
01
01
11
01
2 1
1
1
3 2
10
10
11
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001
5
2 2
11
11
2 3
111
100
3 2
11
01
01
1 3
111
1 1
1
0
----Пример выходных данных-----
1112
1412
3422
3442
NO SOLUTION
1133
1153
2223
2444
|
Линейный вид
