Вступление
Семейство тюленей застряло на айсберге за Полярным кругом. На айсберге находится радиопередатчик, с помощью которого тюлени могут звать на помощь. Однако только папина печать умеет управлять радиопередатчиком. И что еще хуже, в это время года лед очень скользкий, поэтому пломбы будут бесконтрольно скользить, пока не столкнутся с другой пломбой или не соскользнут с края айсберга, из-за чего папа-тюлень будет очень трудно добраться до радиопередатчика. К счастью, одна из печатей - ученый, поэтому она решает написать программу, чтобы выяснить, как маневрировать папиной печатью на радиопередатчик. Поскольку на льду не так много места для написания программы, она решает, чтобы программа использовала как можно меньше байтов.
Описание входа
Программа печати будет принимать входные данные из STDIN, аргументов командной строки или пользовательских функций ввода (например, raw_input()
). Он не может быть предварительно инициализирован в переменной (например, «Эта программа ожидает ввода в переменную x
»).
Первая строка ввода состоит из двух целых чисел, разделенных запятыми, в виде
A,B
Далее следуют B
строки, состоящие из A
символов каждая. Каждая строка может содержать только символы из следующих:
.
Холод, холодно, океан. Карта всегда будет иметь эту границу.#
: Часть айсберга.a
...z
: Печать, которая не является печатью папы на айсберге.D
: Печать папы на айсберге.*
: Радиопередатчик.
(Обратите внимание, что печать папы всегда обозначается заглавной D
буквой. Строчная буква d
- просто обычная печать.)
Описание выхода
В соответствии со следующими правилами относительно того, как пломбы могут двигаться, выведите список инструкций для пломб о том, как они должны двигаться, чтобы получить отцовскую печать на радиопередатчик.
- Правило: все печати могут двигаться вверх (
U
), вниз (D
), влево (L
) и вправо (R
). Они не могут скользить по диагонали. - Правило: После перемещения тюлень будет продолжать двигаться в том же направлении, пока не столкнется с другим тюленем или не упадет в море.
- Если печать сталкивается с другой печатью, она перестает двигаться. Печать, с которой он столкнулся, не будет двигаться.
- Если тюлень упадет в море, он утонет и исчезнет с карты. То есть он не действует как коллайдер для других печатей и не может быть снова перемещен.
- Правило: две печати не могут двигаться одновременно, и печать не может быть перемещена, пока другая еще движется. Следующая печать может быть перемещена только после того, как предыдущая печать перестала двигаться.
- Правило: не существует ограничений в отношении многократного перемещения печати или количества утопающих печатей.
- Правило: правильное решение будет иметь конец папа печать на радиопередатчик. Папа печать не может просто пройти передатчик во время скольжения.
Вывод будет состоять из нескольких строк, каждая в форме
A,B
Где A
это уплотнение для перемещения ( D
для папы печати, a
... z
для других), и B
направление , чтобы переместить печать (или U
, D
, L
или R
). Обратите внимание, что вам не нужно искать кратчайший маршрут. Любой маршрут, который получает отцовскую печать к цели, является приемлемым результатом.
Пример входов и выходов
Входные данные:
25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................
Выход:
D,R
Входные данные:
9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........
Вывод (один возможный вывод из многих):
m,R
b,L
D,U
D,R
D,D
D,L
Входные данные:
26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................
Вывод (один возможный вывод из многих):
v,D
D,L
Если у вас есть другие вопросы, пожалуйста, задавайте в комментариях.
Ответы:
Python 3, 520 байт
Я могу сделать более подробное объяснение позже, если люди захотят, но в основном это запускает поиск в глубину с итеративным углублением в пространстве состояний возможных ходов. Если движение вызывает падение папиной печати, оно немедленно отклоняется. Если папа оказывается рядом с передатчиком, последовательность ходов печатается, и программа делится на ноль, чтобы вызвать выход.
Я могу значительно ускорить выполнение кода, добавив
if G!=g:
в начале второй последней строки 8 дополнительных байтов - это отклоняет ходы, которые ничего не меняют, например,k,L
в первом тестовом примере.Время выполнения заметно меняется от одного прогона к другому, даже с одним и тем же вводом - очевидно, в результате того факта, что я выбираю следующую печать для перемещения путем итерации по a
set
, который является неупорядоченным типом. Я рассчитал второй тестовый пример на 5 минут 30 секунд, хотя в первый раз я не выглядел так долго. С упомянутой выше оптимизацией это больше похоже на 40 секунд.источник
JavaScript (ES6) 322
334 323Edit2 Добавлена анимация во фрагменте
Редактировать Исправлена ошибка, помните начальный posiiton из «*», поэтому я считаю его даже тогда , когда уплотнение скользит по ней и удалить его.
Реализовано как функция с входной строкой в качестве параметра (вероятно, неверно, но ожидает уточнения). Вывод через всплывающее окно.
Проблема с многострочным вводом строк в JavaScript заключается в том, что
prompt
он плохо управляется.Что касается алгоритма: BFS, должен найти оптимальное решение. Я держу в очереди очередь игрового статуса
l
, статус, в котором находится сетка персонажей,g
и последовательность ходовs
. Кроме того, есть набор сеток, полученных до сих пор в переменнойk
, чтобы избежать повторного исследования одной и той же сетки.Основной цикл
Запустите Snippet для тестирования в FireFox
Показать фрагмент кода
источник
C ++, 628 байт
Ну, это не оказалось очень коротким:
Я выбрал C ++, потому что хотел использовать структуры данных (
set
,string
), но по сути он довольно многословен. Решение демонстрирует неплохую производительность, выполняя тест 2 за несколько секунд на MacBook Pro, даже если оно не оптимизировано для работы.Код, прежде чем начать устранять пробелы и некоторые другие сокращения длины:
Основная идея алгоритма заключается в том, что поддерживаются два набора:
q
это набор конфигураций, ожидающих обработки.p
это набор конфигураций, которые были обработаны.Алгоритм начинается с начальной конфигурации в
q
. На каждом этапе извлекается конфигурация из всех возможных перемещений уплотнения иq
добавляется к нимp
, и в результате в нее добавляются новые конфигурацииq
.Тестовый забег:
источник
q
этом смысле лучше использовать FIFO для . Причиной, по которой я использовал набор, было то, что я хотел избежать многократного ввода одной и той же записи. Но у меня появились вторые мысли, когда я увидел результат.