1 Отредактировано Jumbo (2011-06-09 16:04:51)

Тема: Задача "Кодовый замок"

Вот http://informatics.mccme.ru/moodle/mod/ … rid=3022#1
Бьюсь с ней, но никак даже несколько тестов не проходит.
Пытался сделать обходом в глубину из кнопки, но так теряются ответы.
Подскажите как решать!

2

Re: Задача "Кодовый замок"

Нормальная задачка...

Сдалась с такой идеей - сначала генерирую всевозможные замки с длиной K (для K = 10 их не больше 40000)
Для каждого из замков проверяю куда его можно пропихнуть.

3

Re: Задача "Кодовый замок"

Спасибо!
А можно поподробнее про генерацию замков: т.е. для максимум k=10 и поля 30*30 генерируем все множества
из 900 по 10 и отбираем те, что образуют связную область?

4

Re: Задача "Кодовый замок"

Сначало генерируй один длины 1 из них прибавлением всех возможных соседей по ребрy длины 2. итд
на каждом шаге убирай дубликаты. На размер поля на этом шаге не смотри - потом готовые замки двигать будешь

5

Re: Задача "Кодовый замок"

Можно, кстати, написать перебор связных областей так, чтобы он не генерировал повторяющиеся области.

Опишу свою реализацию (пишу по памяти, так что могут быть неточности).

У нас есть очередь кандидатов (изначально в неё добавляется точка (0;0)) - фактически, это точки-окружение текущей связной области в переборе.
Также есть глобальный массив used - в нём мы отмечаем, какие точки мы уже просматривали в текущей ветке перебора (изначально весь used заполнен false, кроме used[0][0] = true).
Перебору передаётся один аргумент - это индекс текущего элемента в очереди, и перебор пробует либо взять этот элемент в текущую область, либо не брать. А если он берёт текущий элемент, то в очередь он добавляет все 4 соседа этой точки, но, конечно, только такие, которые not used (ну и, разумеется, после рекурсивного вызова все добавленные точки надо обратно достать из очереди, сняв с них метку used).

Осталось ещё запретить перебору добавлять точки, меньшие (0;0) - и теперь он точно будет генерировать различные связные области, в которых левая нижняя точка - это точка (0;0).

6

Re: Задача "Кодовый замок"

Красиво. Вроде должно работать smile
Только с левой нижней надо аккуратнее проверять что б не пропустить перевернутую T - как-то
if (y < 0 || y == 0 && x < 0) return

7

Re: Задача "Кодовый замок"

Ну да, это я и имел в виду во фразе "меньшие (0;0)" - точки сравниваются как пары двух чисел.

if (y < 0 || y == 0 && x < 0) return

Наверное, более точно будет сказать, что не добавлять в очередь такие точки - ведь перебору передаётся _кандидат_ на добавление в текущую область (хотя, видимо, ты это же имел в виду)

8

Re: Задача "Кодовый замок"

Спасибо за подробные ответы!
Буду пробовать.

9

Re: Задача "Кодовый замок"

Я не понял про генерацию различных связных областей:
1. Очередь кандидатов очищать при вызове перебора от новой точки?
2. Почему сначала в очереди (0,0), ведь рядом с ней может не быть кнопок?
3. Непонятно вообще как собственно перебирать: если мы берём точку, то как именно перебор пробует взять её, он же должен её брать, так как она соседствует со связной областью? Если добавляем точку в очередь , то перебор вызвать от неё? Остановка когда в очереди k элементов?

10

Re: Задача "Кодовый замок"

1-2: А зачем вызывать перебор от каждой точки заново? Погенерируем все области из точки (0;0), потом попробуем посдвигать каждую полученную область.

3: Очередь содержит лишь кандидатов, т.е. размер очереди - это не количество взятых точек. Перебор заключается в том, какие именно точки среди кандидатов мы берём, при этом когда мы решаем взять какого-либо кандидата, мы тут же докидываем в очередь всех его соседей. Поэтому изначально очередь состоит из одной точки (0;0), которую по предположению всегда надо брать, а затем, по мере того как мы выбираем ещё какие-то точки - очередь разрастается.

11

Re: Задача "Кодовый замок"

Получается генерируются только всевозможные формы областей, т. е. для k=3 будет
1. ###  2. #   3.##   4.#      5.   #    6. ##       ?
               #     #        ##       ##          #
               #

12

Re: Задача "Кодовый замок"

Ну видимо, да, только эти 6 штук.

13

Re: Задача "Кодовый замок"

Спасибо, я сначала не в ту сторону думал по ходу.