Получите эффективную дорогу от точки к точке (BFS на матрице)

Question

У меня есть матрица с 0 и X (0 означает, что вы можете пройти, а X означает стену). У меня есть начальная точка и конечная точка. Я использовал BFS для поиска кратчайшего пути (длины) между началом и концом. (он работает) Но теперь мне нужно найти эффективную дорогу, и я не знаю, как это сделать. (Я думал, что могу использовать алгоритм Ли рекурсив).

Example: 

5 5 
SXXXF 
0XX00 
0XX0X 
0000X 
XXXXX 

Длина: 8 и дорога: (1, 1) -> (2, 1) -> (3, 1) -> (4, 2) -> (4, 3) -> (3, 4) -> (2, 4) -> (1, 5). У меня есть 8 направлений.

Итак, я использовал BFS, чтобы получить длину (8), но я не знаю, как добраться до дороги. Некоторые идеи или псевдокоды? Спасибо!

Answer 1

На самом деле это довольно просто: Храните «предшественника» каждого узла. Будь то в другой матрице, встроенной в исходную карту, или как Map. Даже древовидная структура будет работать, если она двунаправленная.

Без кода я не могу показать вам возможное решение, но в конце все, что вам нужно, это сопоставление node -> node from which it was visited. Например. в вашем примере вы перемещаетесь от (1, 1) до (2, 1), поэтому отображение будет (2, 1)->(1, 1). Это может быть легко реализовано в рамках BFS-процедуры.

Завершите выполнение алгоритма при заполнении картографирования. После этого вы начинаете с поиска предшественника конечного узла, затем предшественника предшественника конечного узла и так далее, пока не вернетесь в начальную точку.