Входные данные:
Лабиринт, содержащий символы:
--(горизонтальная стена);|(вертикальная стена);+(Соединение);(прогулочное пространство);I(Вход);U(выход).
Т.е. вход может выглядеть так:
+--+--+--+--+--+--+--+--+--+--+
I | | |
+ +--+--+--+ + + + +--+ +
| | | | | |
+--+--+--+ +--+--+ + + +--+
| | | | |
+ +--+--+ + +--+--+ +--+ +
| | | | | |
+--+ + +--+--+ +--+--+ + +
| | | | | |
+ +--+--+--+ +--+--+ + + +
| | | | | |
+--+ + +--+--+ +--+--+--+--+
| | | | |
+ + +--+--+--+ +--+ + + +
| | | | | | | |
+--+--+ + +--+ + + +--+ +
| | | | | |
+ +--+--+--+ + + + + +--+
| | | | U
+--+--+--+--+--+--+--+--+--+--+
Выход:
Наиболее эффективный путь , который вы должны пройти , чтобы получить от входа к выходу из лабиринта (через лабиринт), обозначенный обозначающие влево, вправо, вверх и вниз (то есть >; <; ^; v).
Правила соревнований:
- Вы можете принять вход в любом разумном формате. String-array, single String с новыми строками, 2D char-array и т. Д. - все возможные форматы ввода.
- Вывод может состоять из любых четырех разных символов. Т.е.
><^v;→←↑↓;⇒⇐⇑⇓;RLUD;0123;ABCD; так далее.). - Вы можете добавить пробелы или завершающий перевод новой строки в выходной файл, если хотите; это необязательно.
- Шаги подсчитываются за квадрат (см. Четыре
+символа для квадратов), а не за символ. - Лабиринт может быть размером от 5х5 до 15х15 и всегда будет квадратным (поэтому не будет никаких тестов для 5х10 лабиринтов).
- Вы можете предположить, что у каждого лабиринта есть один или несколько допустимых путей от начала до конца, и вы всегда выводите самый короткий (см. Контрольные примеры 4 и 5).
- Если существует несколько путей одинаковой длины, вы можете выбрать, какой из них вывести (см. Контрольный пример 6).
- Вы не можете «выйти» за пределы лабиринта (см. Контрольные примеры 7 и 8).
Основные правила:
- Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте придумать как можно более короткий ответ для «любого» языка программирования. - К вашему ответу применяются стандартные правила , поэтому вы можете использовать STDIN / STDOUT, функции / метод с правильными параметрами, полные программы. Ваш звонок.
- По умолчанию лазейки запрещены.
- Если возможно, добавьте ссылку с тестом для вашего кода.
- Также, пожалуйста, добавьте объяснение, если это необходимо.
Тестовые случаи:
1. Input:
+--+--+--+--+--+--+--+--+--+--+
I | | |
+ +--+--+--+ + + + +--+ +
| | | | | |
+--+--+--+ +--+--+ + + +--+
| | | | |
+ +--+--+ + +--+--+ +--+ +
| | | | | |
+--+ + +--+--+ +--+--+ + +
| | | | | |
+ +--+--+--+ +--+--+ + + +
| | | | | |
+--+ + +--+--+ +--+--+--+--+
| | | | |
+ + +--+--+--+ +--+ + + +
| | | | | | | |
+--+--+ + +--+ + + +--+ +
| | | | | |
+ +--+--+--+ + + + + +--+
| | | | U
+--+--+--+--+--+--+--+--+--+--+
1. Output:
>v>>>vv<v>>v>v>>vvv>>>
2. Input:
+--+--+--+--+--+
I | | |
+ +--+--+ + +
| | | |
+ +--+ + + +
| | | | |
+ + +--+ + +
| | |
+--+ + +--+--+
| | U
+--+--+--+--+--+
2. Output:
>vvv>>v>>>
3. Input:
+--+--+--+--+--+
U | |
+ + +--+--+ +
| | | |
+--+--+ + +--+
| | |
+ +--+--+--+ +
| | | |
+ + + + +--+
| | I
+--+--+--+--+--+
3. Output:
<<<^<v<^^>>^<^<<
4. Input (test case with two valid paths):
+--+--+--+--+--+
U | |
+ + +--+--+ +
| | |
+--+--+ + +--+
| | |
+ +--+--+--+ +
| | | |
+ + + + +--+
| | I
+--+--+--+--+--+
4. Output:
<<^>^<^<<^<< (<<<^<v<^^>>^<^<< is less efficient, and therefore not a valid output)
5. Input (test case with two valid paths):
I
+--+--+--+--+--+--+--+--+--+--+ +--+--+--+--+
| | | | |
+ + + +--+--+--+ + +--+--+ +--+--+ + +
| | | | | | | |
+--+--+--+ +--+ + +--+--+--+--+ +--+--+--+
| | | | | | | | |
+ + + + + +--+ + + + +--+--+ +--+ +
| | | | | | | |
+ +--+--+--+ +--+--+ + +--+ +--+--+ +--+
| | | | | | | | |
+ +--+ + +--+ +--+--+ +--+--+ + +--+ +
| | | | | | |
+ + +--+--+--+--+ + +--+--+--+ +--+ +--+
| | | | | | | |
+--+--+--+ + +--+--+ +--+ + +--+ +--+ +
| | | | | | | |
+ +--+--+--+--+ + + +--+--+--+ + + + +
| | | | | | | | | |
+--+ + + + + + +--+--+ + + +--+ + +
| | | | | | | | | |
+--+ +--+--+ + + + +--+--+--+ + + + +
| | | | | | | | | |
+ +--+ +--+--+ + +--+--+ + +--+ + + +
| | | | | | | | | |
+--+--+--+ + + +--+ + +--+--+ +--+ + +
| | | | | | | |
+ + +--+--+--+--+ +--+--+ +--+--+ +--+ +
| | | | | |
+ + + +--+--+--+--+--+--+--+--+ +--+ +--+
| | | |
+--+--+--+--+--+--+--+--+--+ +--+--+--+--+--+
U
5. Output:
v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv<^<v<<v>v>>>>>>>v (v<<<v<vv<<v<v>>^>>^^>vvv>>>v>vv<vv<<v<v<^<^^^^<vvvvv>v>>>^>>^>^^>vvv<v<v<<v is less efficient, and therefore not a valid output)
6. Input:
+--+--+--+--+--+
I |
+ + + + + +
| |
+ + + + + +
| |
+ + + + + +
| |
+ + + + + +
| U
+--+--+--+--+--+
6. Output:
>>v>v>v>v> or >v>v>v>v>> or >>>>>vvvv> or etc. (all are equally efficient, so all 10-length outputs are valid)
7. Input:
I U
+ + +--+--+--+
| | | |
+ +--+--+ + +
| | | |
+--+ + +--+ +
| | | |
+ +--+ + + +
| | |
+--+ +--+--+ +
| | |
+--+--+--+--+--+
7. Output:
vv>v>^>^<<^
8. Input:
+--+--+--+--+--+
| | |
+ +--+ +--+ +
I | | | |
+ + +--+ + +
U | | | |
+--+--+ + + +
| | | |
+ +--+--+--+ +
|
+--+--+--+--+--+
8. Output:
>v<
Лабиринты генерируются с помощью этого инструмента (а в некоторых случаях слегка модифицированы).
code-golf
path-finding
maze
Кевин Круйссен
источник
источник
v<<<<<<^^^^^(всегда мыслить нестандартно)>v>>>vv<v>>v>v>>vvv>>>.Ответы:
Сетчатка ,
338281275273261 байтПопробуйте онлайн!
Заметки
0x20) заменяются на interpunct (·) как в этом ответе, так и в ссылке TIO. Программа работает нормально, если пробелы восстановлены.AvKrдля вверх, вниз, влево и вправо соответственно. Они могут быть заменены любыми буквами, кромеI.Занимает около 40 секунд на TIO для теста 15 × 15. Потерпи.Переработана часть для поиска кратчайшего пути, как только путь достигнет выхода. Оказывается, это заняло много времени.объяснение
Программа состоит из 3 этапов:
Формат
Поскольку оригинальный формат лабиринта довольно громоздкий, первая часть программы преобразует его в другой формат.
ячейки
В исходном формате каждая ячейка представлена областью 2 × 3:
Поскольку правый столбец не содержит информации, программа идентифицирует ячейки как любую область 2 × 2 с
+символом слева вверху.Это оставляет нам 3 вида клеток:
Uв тестовом примере 1 находится в R-ячейке.В новом формате ячейки представлены в виде строки переменной длины:
Левая и верхняя стены скопированы из оригинального формата. Номер столбца основан на горизонтальном положении ячейки и используется для выравнивания (идентифицируя ячейки непосредственно друг над другом). Путь - это алфавитная строка, используемая на этапе заполнения для сохранения кратчайшего пути к этой ячейке. Маркер пути и выхода будет дополнительно объяснен.
Половина клеток
Хотя большая часть лабиринта является клеткой, существуют области лабиринта, которые не являются клетками:
+s вдоль правой стены не образуют ячеек, поскольку они находятся в последнем столбце.+как слева от них нет. Например, входIв контрольном примере 1 находится в полукадре L.Технически, есть T полуклеток над лабиринтом (когда есть верхнее заполнение) и B полуклеток (вдоль нижней стенки, когда нет нижнего заполнения), но они не представлены в новом формате.
Верхний ряд полуклетки будет удален как часть построения полных ячеек в той же строке, поэтому полуклетки представлены в новом формате как
Полуклетки R это просто
|. L-полуклетка имеет толькоIпуть, только маркер выхода и пустой путь, или просто пустую стену.Входы и выходы
Если вход находится слева, справа или снизу от лабиринта, то маркер входа
Iбудет естественным образом включен в (половину) ячейку как путь, который можно удалить при возврате последнего пути.Если вход выше лабиринта, первый (нисходящий) шаг делается во время фазы строительства, так как Т-полуклетки удаляются во время строительства. Это сохраняет работоспособный путь в полной ячейке. Верхняя стена закрыта после.
Если выход находится слева, справа или снизу от лабиринта, то
U, естественно, будет включен в (половину) ячейки. Чтобы избежать ошибки в качестве пути,&вместоU. Используется маркер выхода, не являющийся алфавитом . Маркер выхода встраивается в ячейку или половину ячейки (как указано выше).Если выход находится над лабиринтом, то это будет единственное отверстие, которое может пройти над верхним рядом ячеек (поскольку отверстие для входа, если оно есть, уже будет закрыто). Любой путь, достигающий этой дыры, может выйти из лабиринта, сделав шаг вверх.
Наконец, любая B-ячейка, содержащая вход или выход, должна закрывать свою левую стену, чтобы предотвратить «решение» лабиринта, проходя вдоль B-ячеек. Входы и выходы в R-ячейках или L-полуклетках не требуют дальнейшей обработки, поскольку алгоритм заливки не допускает вертикальных перемещений к ним и из них.
пример
Как пример, первый тестовый пример
является
в новом формате. Вы можете конвертировать другие лабиринты здесь .
Этап строительства
Этап строительства составляет первые 13 строк программы.
Конвертирует выход в L Полуклетка в маркер выхода
Добавляет стены слева от входа и выхода в ячейках B
Делает первый шаг, если вход выше лабиринта
Выполняет фактическое преобразование
Закрывает отверстие верхнего входа
Сохраняет только строки с
1. Поскольку лабиринты имеют ширину не менее 5 ячеек, а номера столбцов появляются с шагом 3, строка с ячейками нового формата должна содержать номер столбца от 10 до 19.Преобразует выход в ячейку R или ячейку B для маркера выхода
Заполнить фазу
Фаза заполнения составляет следующие 8 строк программы. Он использует алгоритм заливки, чтобы заполнить все ячейки кратчайшим путем, чтобы добраться туда от входа.
Помещает всю фазу заполнения на петлю, чтобы заполнить весь лабиринт.
Каждая клетка, способная двигаться влево, делает это. Клетка может двигаться влево, если
Затем каждая клетка, способная двигаться вправо, делает это. Клетка может двигаться вправо, если
Затем каждая клетка, способная двигаться вниз, делает это. Клетка может двигаться вниз, если
Обратите внимание, что L-полуклетки не могут двигаться вниз, так как у них нет номеров столбцов.
Затем каждая клетка, способная двигаться вверх, делает это. Клетка может двигаться вверх, если
Фаза возврата
Фаза возврата составляет последние 5 строк программы. Эта фаза ищет и возвращает путь, заполненный в выходной ячейке.
Схема пути на выходе зависит от того, где находится выход:
& <path><left wall> <column number> & <path><left wall> <column number> · <path>в верхнем ряду.Находит ячейку в верхней строке с пустой верхней стенкой и непустым путем. Это позаботится о последнем случае, добавив последний шаг и маркер выхода.
Соответствует и возвращает непустой путь после маркера выхода.
Удаляет маркер выхода и
Iпрефикс пути.источник
AvKr? Имеют ли они значение / являются ли они аббревиатурами вверх, вниз, влево и вправо на вашем родном языке, или есть другая причина, по которой вы выбрали именно эти символы?AvKrближе всего к стрелкам в алфавите.Perl 6 ,
259295 байтКак это работает
Это сжимает лабиринт, так что внутри каждой ячейки 1x1 вместо 2x1 пробелов:
Это рекурсивная функция поиска пути. Он принимает три параметра: текущую координату
c=(y,x), список уже посещенных координатvи пройденный путьp(в виде списка символов стрелки).Если символ в текущей координате является пробелом, он возвращается к своим четырем соседям.
Если символ с текущей координатой является a
I, он возвращается к двум соседям, которые не «вдоль края», чтобы заставить решения пройти через лабиринт, а не вокруг него.Если символ в текущей координате является a
U, он вызываетtakeнакопленную строку пути.Рекурсивная функция первоначально вызывается с координатой буквы
I, которая находится с помощью регулярного выражения.gatherКлючевое слово собирает все ценности , на которыхtakeбыли называемыми внутри функции, то есть весь допустимый нециклических путь через лабиринт.Выбирается кратчайший путь, каждая вторая стрелка отбрасывается, чтобы учесть тот факт, что для перехода из одной ячейки в другую требуется два одинаковых хода, а оставшиеся стрелки объединяются для формирования строки, возвращаемой из лямбды.
источник
Python 2: 302 байта
Принимает входные данные в виде массива строк одинаковой длины. Отпечатки
0вправо,1вниз,2влево и3вверх.объяснение
Я выбрал другой подход, чем другие ответы. Общая идея: рекурсивный поиск, находя кратчайший путь между движением прямо вперед и поворотом доски на 90 градусов.
Попробуйте онлайн!
источник
Iчтобы предотвратить выход пути из лабиринта. Приятного пребывания и +1 от меня. :)JavaScript (ES6), 356 байт
Принимает ввод как двумерный массив символов. Каждая строка должна быть дополнена слева одним пробелом и не должна заканчиваться пробелом, независимо от того, где находятся начальная / конечная точки.
Использует идею smls о том, чтобы сжать лабиринт, чтобы сделать каждую ячейку 1x1 и убрать повторяющиеся стрелки из выходных данных.
Неуправляемый и объясненный
Тестовый фрагмент
Показать фрагмент кода
источник
Сетчатка , 416 байт
Попробуйте онлайн!Если бы я видел этот вопрос, когда он был первоначально опубликован, это, вероятно, ответ, который я бы дал, так что я все равно его отправляю, хотя в Retina есть гораздо лучший ответ. Объяснение:
Заполните границу. Это позволяет избежать прогулки по внешней стороне лабиринта (например, для контрольного примера 7).
Поместите не алфавитный маркер на входе.
Наводнение заполните от выхода до входа. На каждом шаге используйте букву, чтобы указать наилучшее направление (разве - это может быть знакомо геймерам; я также подумал о hjkl, но нашел его слишком запутанным). Кроме того, предпочитайте повторять в том же направлении; это позволяет избежать перехода влево / вправо между двумя вертикально смежными ячейками.
Предположим, что первый шаг вниз.
Но если есть буква выше, слева или справа от входа, измените это на первый шаг.
Переместите маркер в направлении последнего движения, считывая направление следующего движения от квадрата, к которому движется маркер, и добавьте его в список направлений. Это повторяется до
Uбудет достигнуто.Удалите все после указаний, поскольку это больше не нужно.
Исходная сетка имеет макет 3 × 2. При перемещении по вертикали, если мы делаем зигзаг по горизонтали, заливка будет оптимизировать движение и перемещать только 3n-1 символов по горизонтали, поэтому при делении на три нам нужно округлить. Вертикально мы просто делим на 2.
Я также исследовал реальное решение с квадратной сеткой, то есть там, где матрица символов сама по себе квадратная, а не как макет 3 × 2 с необязательной рамкой. Возможно, это не соответствовало этому вопросу, но возможность транспонирования позволила уменьшить количество байтов до 350: попробуйте онлайн!
источник
-символа для входа и выхода. Поскольку задача в основном состоит в том, чтобы пройти лабиринт, я думаю, это нормально, но мне интересно: какие были проблемы, когда вы не разместили эти стены выше / нижеIиU? Кроме того, не могли бы вы проверить, что это работает для контрольного примера 7 сIиUвверху вместо сторон? TIO превышает 60-секундный лимит, поэтому я не могу проверить это сам. Хотя вы читаете ваше объяснение первой попытки отключиться по умолчанию, я предполагаю, что она должна работать нормально.