Форум программистов, компьютерный форум CyberForum.ru

Задачка на иниересную тему - C++

Восстановить пароль Регистрация
 
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 42
04.09.2013, 16:58     Задачка на иниересную тему #1
Доброго времени суток.

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

Текст задачи:

Через прямоугольник, все четыре стороны которого раскрашены в разные цвета, провели несколько разрезов, параллельных его сторонам. После этого получившиеся маленькие прямоугольники перемешали и, возможно, несколько раз повернули на 90 градусов по часовой стрелке.

Ваша задача — восстановить прямоугольник, если это возможно. Заданные прямоугольники разрешается вращать по часовой стрелке на 90 градусов от 0 до 3 раз. Два маленьких прямоугольника в собранном прямоугольнике могут иметь общую сторону только в том случае, если эта сторона бесцветна. В собранном прямоугольнике должны быть использованы все заданные маленькие прямоугольники, ничего не должно остаться. Стороны собранного прямоугольника должны быть раскрашены в различные цвета, каждая сторона в свой цвет.

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

Первая строка входного файла содержит одно целое число N — количество имеющихся маленьких прямоугольников (1 ≤ N ≤ 103).
Следующие N строк задают маленькие прямоугольники. Каждый прямоугольник описывается на отдельной строке. Его описание состоит из последовательности, содержащей два целых числа w и h, за которыми идут четыре буквы c0, c1, c2 и c3, записанные через пробел. w и h задают ширину и высоту прямоугольника (1 ≤ w, h ≤ 105), а буквы — цвета сторон его в порядке обхода по часовой стрелке, начиная с верхней стороны прямоугольника. c[j] может принимать значения {R, G, B, Y, N} (0 ≤ j ≤ 3), где R, G, B, Y — цвета сторон исходного прямоугольника, а N обозначает отсутствие цвета.

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

Если восстановить прямоугольник, используя все заданные прямоугольники, невозможно, то в выходной файл нужно вывести единственную строку IMPOSSIBLE.
В противном случае необходимо вывести N строк, которые описывают положение заданных маленьких прямоугольников в собранном прямоугольнике в порядке их перечисления во входном файле. Совместим начало координат с левым нижним углом собранного прямоугольника, ось OX пойдет по нижней его стороне, а ось OY — по левой вертикальной стороне. Тогда каждая строка будет содержать описание положения одного маленького прямоугольника в результирующем. Описание должно состоять из трех целых чисел, записанных через пробел. Первые два числа x и y задают координаты левого нижнего угла соответствующего прямоугольника в собранном прямоугольнике, а третье число r — количество его вращений по часовой стрелке (0 ≤ x, y ≤ 105, 0 ≤ r ≤ 3).
Если существует несколько способов собрать прямоугольник, то выведите любой.



Вот думал, каким образом её решать... Может через графы, но тогда что выбрать за вершины и каким образом обходить? Можно перебором, но тут никак в голове не складывается картина логики перебора((

Если у кого есть идеи, поделитесь плз. Заранее всем благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.09.2013, 16:58     Задачка на иниересную тему
Посмотрите здесь:

C++ задача на тему строки
C++ задачка на тему строк
Задание на тему «Структуры» C++
Задача на тему массива C++
C++ программа на тему строки!
Code:: Blocks (не на тему программирования, а на тему настройки) C++
C++ Нужно найти тему

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Raali
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 1
04.09.2013, 17:27     Задачка на иниересную тему #2
во первых нужно создать функцию определения для каждого прямоугольника какой цвет какого размера
потом для одинаковых цветов во всех прямоугольниках сложить размеры, должно образоваться 4 разных числа, потом проверить что существует 2 эквивалентных пары (т.е две ширины и две высоты одинакового размера), если это условие не выполняется, то IMPOSSIBLE.... а вот как центральные прямоугольники считать это я не знаю)
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 42
05.09.2013, 13:33  [ТС]     Задачка на иниересную тему #3
Спасибо за ответ, но немного не понял, какие 4 числа должны получиться и такие задачи обычно (это базовая задача, просто я нет знаю, на какую тему) решаются одним универсальным алгоритмом (возможно просто алгоритм состоит из множества условий)...
Насколько я понимаю, здесь должен быть перебор вариантов компановок этих маленьких прямоугольников. Два прямоугольника могут соединяться только вершинами с 'N', помимо этого при их соединении справа и слева от вершины 'N' должны быть одинаковые цвета...
Но вот проблема в том, что я не могу уложить в голове это построение... Мало того там какие - то повороты... Очень напоминае теорию графов, но вот как реализовать, большой вопрос...

P.S Но если меня просто заело на графах, то лучше, конечно, будет какой-нибудь алгоритм без них...
Yandex
Объявления
05.09.2013, 13:33     Задачка на иниересную тему
Ответ Создать тему
Опции темы

Текущее время: 04:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru