Оптимальный алгоритм решения лабиринта без поворота влево

Я работаю над проектом, в котором мне нужно решить лабиринт, используя минимальное количество поворотов вправо и без поворотов влево.

Пройденное расстояние не имеет значения, если свести к минимуму правые повороты. Нас просят реализовать нашу программу, используя как алгоритм поиска с возвратом, так и оптимальный (по времени) алгоритм.

Для алгоритма поиска с возвратом я собирался использовать стек. Мой алгоритм был бы примерно таким:

• Вставить все четыре возможных начальных направления в стек.
• Следуйте по пути, по возможности двигаясь прямо.
• Если мы дойдем до конца лабиринта, верните текущую длину пути как лучшую.
• Если мы дойдем до тупика, вернитесь к последнему возможному повороту направо и it.
• Если текущая длина пути больше, чем текущая лучшая, вернуться к последнему возможному повороту направо и свернуть на него.

Мне было интересно, может ли кто-нибудь указать мне направление оптимального алгоритма для этого.

Мне сложно придумать что-нибудь получше, чем возвращение.