В этом алгоритме я пытаюсь найти кратчайший путь из заданной начальной точки (S) и заданной конечной точки (D) для заданного 2D-массива, имея в виду, что некоторые элементы в массиве (*) считаются препятствиями. Обычно я бы выполнил типичный BFS и вернул расстояние кратчайшего пути, но есть небольшая морщина. Мне нужно показать кратчайший путь (и), пройденный путем замены пройденного элемента кардинальным направлением (север, юг, восток или запад. Сокращенно n, s, e, w соответственно), по которому путь ведет к месту назначения. В случае нескольких кратчайших путей, по которым вы можете пойти ЛИБО на юг или восток, чтобы достичь цели, элемент будет заполнен комбинацией сторон света, то есть такими, как показано на втором рисунке. ОБРАТИТЕ ВНИМАНИЕ, что это не означает юго-восток, поскольку диагональные обходы не допускаются. Я знаком с использованием BFS в алгоритмах, но я немного застрял в том, как я отмечаю путь (пути), пройденный с помощью направления включены. Я не обязательно ищу полноценный алгоритм для ответа на этот вопрос, я скорее ищу ответ в виде псевдокода, который направит меня на верный путь. Первое изображение представляет собой образец входного массива, а второе изображение - решение указанного входного массива. TL: DR Я прошу совета относительно того, как отслеживать направления, взятые через сетку при выполнении BFS. Любая помощь / отзывы приветствуются и заранее благодарны!
