Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 24.03.2010, 17:10
RuslanNiger

 
Сообщений: n/a

Задача - головоломка
Помогите решить задачу. Даже не знаю как подступиться.

Имеется головоломка из пяти кусочков, которые нужно составить в квадрат.
При составлении квадрата
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
  #2  
Старый 24.03.2010, 17:42
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

1. Посчитать единички, и убедиться, что их количество - полный квадрат
2. Проверить, что ни в одном куске нет размерности, большей стороны квадрата
3. Кусков всего 5, так что перебор вполне подойдет.
Один из кусков должен быть в нижнем левом углу. Перебираем их, для каждого начального пытаемся приставить другие справа и сверху (и снизу, если там осталась пустота) и т.д.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Головоломка с линейной алгеброй midi Задачи 3 13.02.2010 18:08
Головоломка про ферзей гость Задачи 5 09.04.2008 02:51