Тема: Задача "Кодовый замок"
Вот http://informatics.mccme.ru/moodle/mod/ … rid=3022#1
Бьюсь с ней, но никак даже несколько тестов не проходит.
Пытался сделать обходом в глубину из кнопки, но так теряются ответы.
Подскажите как решать!
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Задача "Кодовый замок"
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Вот http://informatics.mccme.ru/moodle/mod/ … rid=3022#1
Бьюсь с ней, но никак даже несколько тестов не проходит.
Пытался сделать обходом в глубину из кнопки, но так теряются ответы.
Подскажите как решать!
Нормальная задачка...
Сдалась с такой идеей - сначала генерирую всевозможные замки с длиной K (для K = 10 их не больше 40000)
Для каждого из замков проверяю куда его можно пропихнуть.
Спасибо!
А можно поподробнее про генерацию замков: т.е. для максимум k=10 и поля 30*30 генерируем все множества
из 900 по 10 и отбираем те, что образуют связную область?
Сначало генерируй один длины 1 из них прибавлением всех возможных соседей по ребрy длины 2. итд
на каждом шаге убирай дубликаты. На размер поля на этом шаге не смотри - потом готовые замки двигать будешь
Можно, кстати, написать перебор связных областей так, чтобы он не генерировал повторяющиеся области.
Опишу свою реализацию (пишу по памяти, так что могут быть неточности).
У нас есть очередь кандидатов (изначально в неё добавляется точка (0;0)) - фактически, это точки-окружение текущей связной области в переборе.
Также есть глобальный массив used - в нём мы отмечаем, какие точки мы уже просматривали в текущей ветке перебора (изначально весь used заполнен false, кроме used[0][0] = true).
Перебору передаётся один аргумент - это индекс текущего элемента в очереди, и перебор пробует либо взять этот элемент в текущую область, либо не брать. А если он берёт текущий элемент, то в очередь он добавляет все 4 соседа этой точки, но, конечно, только такие, которые not used (ну и, разумеется, после рекурсивного вызова все добавленные точки надо обратно достать из очереди, сняв с них метку used).
Осталось ещё запретить перебору добавлять точки, меньшие (0;0) - и теперь он точно будет генерировать различные связные области, в которых левая нижняя точка - это точка (0;0).
Красиво. Вроде должно работать
Только с левой нижней надо аккуратнее проверять что б не пропустить перевернутую T - как-то
if (y < 0 || y == 0 && x < 0) return
Ну да, это я и имел в виду во фразе "меньшие (0;0)" - точки сравниваются как пары двух чисел.
if (y < 0 || y == 0 && x < 0) return
Наверное, более точно будет сказать, что не добавлять в очередь такие точки - ведь перебору передаётся _кандидат_ на добавление в текущую область (хотя, видимо, ты это же имел в виду)
Спасибо за подробные ответы!
Буду пробовать.
Я не понял про генерацию различных связных областей:
1. Очередь кандидатов очищать при вызове перебора от новой точки?
2. Почему сначала в очереди (0,0), ведь рядом с ней может не быть кнопок?
3. Непонятно вообще как собственно перебирать: если мы берём точку, то как именно перебор пробует взять её, он же должен её брать, так как она соседствует со связной областью? Если добавляем точку в очередь , то перебор вызвать от неё? Остановка когда в очереди k элементов?
1-2: А зачем вызывать перебор от каждой точки заново? Погенерируем все области из точки (0;0), потом попробуем посдвигать каждую полученную область.
3: Очередь содержит лишь кандидатов, т.е. размер очереди - это не количество взятых точек. Перебор заключается в том, какие именно точки среди кандидатов мы берём, при этом когда мы решаем взять какого-либо кандидата, мы тут же докидываем в очередь всех его соседей. Поэтому изначально очередь состоит из одной точки (0;0), которую по предположению всегда надо брать, а затем, по мере того как мы выбираем ещё какие-то точки - очередь разрастается.
Получается генерируются только всевозможные формы областей, т. е. для k=3 будет
1. ### 2. # 3.## 4.# 5. # 6. ## ?
# # ## ## #
#
Спасибо, я сначала не в ту сторону думал по ходу.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Задача "Кодовый замок"