Кратчайший путь прямоугольного кубоида в доске

#breadth-first-search #shortest-path #dijkstra #a-star

Вопрос:

У меня есть проблема с алгоритмами кратчайшего пути. У меня есть прямоугольный кубоид на доске (скриншот прилагается), движение куба выполняется вращением по одному из краев. Таким образом, в зависимости от состояния куб может занимать 2 плитки на доске или стоять на одной плитке доски. При каждом вращении размер (в плитках) следующего движения может изменяться. Существует ли какой-либо алгоритм, способный вычислить кратчайший путь с таким поведением? Любая помощь приветствуется.

1. Похоже на Блоксорца. Я не понимаю, почему BFS или A* не сработали бы. Посмотрите эту статью , которую я еще не читал, но она выглядит многообещающей.

2. @ggorlen эта статья-именно то, что я искал. И я нашел ката с аналогичной проблемой codewars.com/kata/5a2a597a8882f392020005e5/train/kotlin Спасибо! Если вы опубликуете ответ, я отмечу его как выбранный.

Ответ №1:

Да, это можно сделать с помощью BFS. В очереди нам нужно поддерживать кортеж «состояние кубоида» «Текущие ячейки кубоида», и нам нужно выяснить, в какие следующие ячейки кубоид может перейти и в какое состояние, и поместить его в очередь. Это стандартный поисковый вопрос Первой Широты.