кратчайший путь через лабиринт

Question

Я работаю над проектом, в котором я должен пройти лабиринт, используя правило левой руки, и на основе пересечений, с которыми сталкивается программа, мне нужно создать узел для соединения с графом, который я затем определю кратчайшим путем.Цель состоит в том, чтобы программа прошла через лабиринт, затем закрыла программу и прочитала файл, который содержит график и определяет кратчайший путь к финишу.то, что я сделал, я могу пройти через лабиринт, используя правило левой руки.Что я думаю сделать, так это создать узел, когда я найду перекресток, и после каждого перемещения программы я увеличиваю стоимость этого пути на единицу.На заметку: нужна ли вам матрица смежности при использовании алгоритма Дейкстры?

Answer 1

Попробуйте что-то вроде этого, оно должно работать:

0 - create an empty "solution path" stack of location objects.

1 - if current position is maze exit, return "solution path" stack.

2 - wall in front? turn left and repeat 2, else continue to 3.

3 - if current position is at top of "solution path" stack, 
       pop it off of the stack
       else push it onto the stack 

4 - move forward.

Когда вы проверяете вершину стека на текущую позицию, вам может потребоваться проверить элемент непосредственно перед самой последней, поскольку последняя будет позицией, которую вы только что покинули.